Part 1

首先，化简题目中的式子：

$$\begin{aligned} \text{原式} &=\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{i}\sum\limits_{k=1}^{j} \sum\limits_{l=1}^{k} {\left( \frac{ij}{k}+\prod\limits_{p=1}^{j}\begin{cases}p^2&2\mid p\\p&2\nmid p\end{cases}\text{ }\right)}\\ &=\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{i}\sum\limits_{k=1}^{j} {\left( ij+j!\times\lfloor\frac{j}{2}\rfloor!\times2^{\lfloor\frac{j}{2}\rfloor}\times k \right)} \\ &=\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{i}\left(ij^2+ j!\times\lfloor\frac{j}{2}\rfloor!\times2^{\lfloor\frac{j}{2}\rfloor}\times\frac{j(j+1)}{2}\right) \\ &=\sum\limits_{i=1}^{n} \left(\frac{i^2(i+1)(2i+1)}{6}+ \sum\limits_{j=1}^{i} {\left(j!\times\lfloor\frac{j}{2}\rfloor!\times2^{\lfloor\frac{j}{2}\rfloor}\times\frac{j(j+1)}{2}\right)}\right) \\ &=\sum\limits_{i=1}^{n}{\left(\frac{i^2(i+1)(2i+1)}{6}\right)}+\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{i} {\left(j!\times\lfloor\frac{j}{2}\rfloor!\times2^{\lfloor\frac{j}{2}\rfloor}\times\frac{j(j+1)}{2}\right)} \end{aligned} $$

Part 2

可以看到，式子好求了很多，许多项都可以预处理。于是有：

• $a(i)=i!$

• $b(i)=2^i$

• $c(i)=\sum\limits_{j=1}^{i} {\left(a(j)\times a(\lfloor\frac{j}{2}\rfloor)\times b(\lfloor\frac{j}{2}\rfloor)\times\frac{j(j+1)}{2}\right)}$

• $d(i)=\sum\limits_{j=1}^{i} c(j)$

• $e(i)=\sum\limits_{j=1}^{i}{\left(\frac{j^2(j+1)(2j+1)}{6}\right)}$

• $f(i)=e(i)+d(i)$

然后，就没有然后了。

Part 3

std：

#include <bits/stdc++.h>
using namespace std;
const int N = 1000000;
long long ttn[N + 5], p2[N + 5], pta[N + 5], ptb[N + 5], preptb[N + 5], ans[N + 5];
//        ---a(i)---  --b(i)---  ---e(i)---  ---c(i)---  ----d(i)-----  ---f(i)---
int main() {
	int n, m;
	cin >> n >> m;
	ttn[0] = p2[0] = 1;
	for (int i = 1; i <= N; i ++)
		ttn[i] = ttn[i - 1] * i % m;
	for (int i = 1; i <= N; i ++) {
		p2[i] = p2[i - 1] + p2[i - 1];
		if (p2[i] >= m) p2[i] -= m;
	}
	for (int i = 1; i <= N; i ++) {
		long long res = 1;
		res *= i, res *= i, res %= m;
		res *= (i + 1), res %= m;
		res *= (i + i + 1), res %= m;
		while (res % 6) res += m;
		res /= 6;
		pta[i] = pta[i - 1] + res;
		if (pta[i] >= m) pta[i] -= m;
	}
	for (int i = 1; i <= N; i ++) {
		long long res = 1;
		res *= ttn[i], res *= ttn[i >> 1], res %= m;
		res *= p2[i >> 1], res %= m;
		res *= i, res %= m;
		res *= (i + 1), res %= m;
		if (res & 1) res += m;
		res >>= 1;
		ptb[i] = ptb[i - 1] + res;
		if (ptb[i] >= m) ptb[i] -= m;
	}
	for (int i = 1; i <= N; i ++) {
		preptb[i] = preptb[i - 1] + ptb[i];
		if (preptb[i] >= m) preptb[i] -= m;
	}
	for (int i = 1; i <= N; i ++) {
		ans[i] = preptb[i] + pta[i];
		if (ans[i] >= m) ans[i] -= m;
	}
	for (int i = 1; i <= n; i ++)
		cout << ans[i] << endl;
    return 0;
}

定义：

$$f(n) = \sum_{1 \leq l \leq k \leq j \leq i \leq n}(\dfrac{ij}{k} + \prod_{p=1}^{j}\begin{cases}p^2&2\mid p\\p&2\nmid p\end{cases}) $$

试求 $f(1) \sim f(n)$ 的值。答案对一个给定的质数 $m$ 取模。

要求 $\Theta(n)$ 解法。

---

缝合怪。

前半部分：

$$\begin{aligned} f_1(n) &= \sum_{1 \leq l \leq k \leq j \leq i \leq n}\dfrac{ij}{k} \\ &= \sum_{1 \leq k \leq j \leq i \leq n} \sum_{l=1}^k \dfrac{ij}{k} \\ &= \sum_{1 \leq k \leq j \leq i \leq n}ij \\ &= \sum_{j=1}^n \dfrac{(j+n)(n-j+1)j^2}{2} \\ \end{aligned} $$

上面一步的变形是枚举 $j$，则当 $j$ 固定时，原式首先 $\times j^2$（一个 $j$ 是 $ij$ 的 $j$，一个 $j$ 是 $k$ 的取值范围为 $1 \sim j$），最后乘法分配律乘上所有 $i$ 的和（$j + \dots + (n - 1) + n = \dfrac{(j+n)(n-j+1)}{2}$）。

后半部分：令 $p(x) = \prod_{p=1}^{j}\begin{cases}p^2&2\mid p\\p&2\nmid p\end{cases}$。

$$\begin{aligned} f_2(n) &= \sum_{1 \leq l \leq k \leq j \leq i \leq n}p(j) \\ &= \sum_{j=1}^n \dfrac{j(j+1)(n-j+1)}{2}p(j) \\ \end{aligned} $$

第二步变形对应枚举 $j$，求 $i, k, l$ 方案数。$i$ 取值范围 $n - j + 1$，$k, l$ 总共有 $\dfrac{j(j+1)}{2}$ 种方案。

考虑这样干瞪眼你什么都无法得到。直接大展开。

$$\begin{aligned} f_2(n) &= \sum_{j=1}^n \dfrac{j(j+1)(n-j+1)}{2}p(j) \\ &= \sum_{j=1}^n \dfrac{-j^3+j^2n+jn+j}{2}p(j) \\ \end{aligned} $$

错位相减。

$$\begin{aligned} f_2(n) - f_2(n-1) &= \sum_{j=1}^n \dfrac{-j^3+j^2n+jn+j}{2}p(j) - \sum_{j=1}^{n-1} \dfrac{-j^3+j^2(n-1)+j(n-1)+j}{2}p(j) \\ &= \dfrac{n^2+n}{2}p(n) - \sum_{j=1}^{n-1} \dfrac{j^2+j}{2}p(j) \\ \end{aligned} $$

第一项是前一个 $\sum$ 的 $j=n$ 情况。后面的 $\sum$ 是两个求和每一项相减。

直接做一个 $\dfrac{i^2+i}{2}p(i)$ 前缀和即可。

所以每次能从 $f_1(n-1), f_2(n-1)$ 常数时间复杂度转移到 $f_1(n), f_2(n)$。

如果每个式子只写一步，是 $\Theta(n^2)$ 的。