【题解】P6042 「ACOI2020」学园祭

link

题意

求
$$\sum _{i=1}^n\sum _{j=1}^i\sum _{k=1}^j\gcd ((i-j)!,(j-k)!)$$
$T$ 组数据。$T,n\le 10^6$。

题解

易得
$$ans=\sum _{i=1}^n\sum _{j=1}^i\sum _{k=1}^j\min (i-j,j-k)!$$
记 $x=i-j,y=j-k$。显然 $x,y\ge 0,x+y=i-k\le n-1$。

那么 $0\le \min (x,y)\le \lfloor \frac{n-1}{2}\rfloor$。

考虑枚举 $d=\min (x,y)$，计算对于每个 $d$ 有多少种 $i,j,k$ 的取值方案 $cn{t}_d$。
$$ans=\sum _{d=0}^{\lfloor \frac{n-1}{2}\rfloor }d!\cdot cn{t}_d$$
对于一组确定的 $x,y$，若我们能确定 $k$ 的值，那么有 $j=y+k,i=x+j=x+y+k$，也就是确定一个 $k$ 即可确定一组 $i,j,k$。因为 $i\le n$，所以 $x+y+k\le n$，所以 $k\le n-x-y$。即对于一组确定的 $x,y$，有 $n-x-y$ 组 $i,j,k$ 与之对应。

考虑对于确定的 $d$，有多少组 $x,y$。不妨假设 $x=d$，则 $y$ 显然满足 $y\ge d$，因为 $x+y\le n-1$，所以 $d\le y\le n-x-1$，所以 $y$ 有 $n-x-1-d+1=n-x-d=n-2d$ 种取值。那么对于所有的 $d$，当 $x=d$ 时总共的方案为 $\sum _{d}n-2d=\frac{(n-2d+1)(n-2d)}{2}$。$x$ 取 $d$ 与 $y$ 取 $d$ 的方案是一样的，所以直接乘 $2$。注意这里对于 $x=y=d$ 的方案算了两次，减去 $n-2d$ 即可。

现在有
$$cn{t}_d=2\cdot \frac{(n-2d+1)(n-2d)}{2}-(n-2d)=(n-2d{)}^2$$
所以现在有
$$ans=\sum _{d=0}^{\lfloor \frac{n-1}{2}\rfloor }d!\cdot (n-2d{)}^2$$
看起来现在可以 $O(Tn)$ 解决这个问题了。

只需要再进一步推导：
$$\begin{gathered} ans=\sum _{d=0}^{\lfloor \frac{n-1}{2}\rfloor }(n^{2}d!-d!4nd+d!4d^2) \\ =n^2\sum _{d=0}^{\lfloor \frac{n-1}{2}\rfloor }d!-4n\sum _{d=0}^{\lfloor \frac{n-1}{2}\rfloor }d!\cdot d+4\sum _{d=0}^{\lfloor \frac{n-1}{2}\rfloor }d!\cdot d^2 \end{gathered}$$
于是只需要预处理三个 $\sum$ 的前缀和就能 $O(1)$ 询问啦。总时间复杂度 $O(n+T)$。

实现

注意阶乘求和不要忘了 $0$ 的阶乘。long long 要开够。

然鹅我把 $\lfloor \frac{n-1}{2}\rfloor$ 写成了 $\lfloor \frac{n}{2}\rfloor$ 竟然还过了。

#include 
using namespace std;
typedef long long LL;
const int N = 1000005;
const LL mod = 10086001;
int T;
LL f1[N], f2[N], sf[N], n;
void init() {
	sf[0] = 1;
	for (LL i = 1, fac = 1; i < (N >> 1); i++, fac = fac * i % mod)
		sf[i] = (sf[i - 1] + fac) % mod,
		f1[i] = (f1[i - 1] + i * i % mod * fac) % mod,
		f2[i] = (f2[i - 1] + i * fac) % mod;
}
int main() {
	init();
	scanf("%d", &T);
	while (T--)
		scanf("%lld", &n),
		printf("%lld\n", ((n * n % mod * sf[(n - 1) >> 1] % mod + 4 * f1[(n - 1) >> 1] % mod - 4 * n * f2[(n - 1) >> 1] % mod) % mod + mod) % mod);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

总结

• 这题只要敢推式子就能做。思路非常明显。