题解 P6042 【「ACOI2020」学园祭】
Alex_Wei
·
·
题解
写篇小学生也能看懂的题解，不需要找规律。
虽然看起来有一丢丢麻烦，但如果你认真读一定能看懂 ~
---
首先化简一下题目给出的柿子
$$\sum_{i=1}^n\sum_{j=1}^i\sum_{k=1}^j\gcd(\frac{(i-j)!}{j!}\times j!,\frac{(j-k)!}{k!}\times k!)$$
即
$$\sum_{i=1}^n\sum_{j=1}^i\sum_{k=1}^j\gcd((i-j)!,(j-k)!)$$
即
$$\sum_{i=1}^n\sum_{j=1}^i\sum_{k=1}^j\min(i-j,j-k)!$$
感觉题目直接给出上式就行了，~~学过数学的都会化简吧。~~
但上面这坨柿子感觉不太可做的样子，看来是我太弱了$\rm{.webp}$。
- 为了说明方便，在下文中我们定义 $x$ 为 $i-j$，$y$ 为 $j-k$。
---
$$\sum_{i=1}^n\sum_{j=1}^i\sum_{k=1}^j\min(x,y)!$$
不难发现 $x,y$ 一定满足以下条件：
- $x,y$ 为非负整数。（废话
- $x+y\leq n-1$。
于是乎，我们就知道 $\min(x,y)$ 的最大值不会超过 $\lfloor\frac{n-1}{2}\rfloor$。
然后柿子就可以化简为这样：
$$\sum_{a=0}^{\lfloor\frac{n-1}{2}\rfloor}a!\times z_a$$
其中 $z_a$ 为当 $\min(x,y)=a$ 时 $i,j,k$ 共有多少种取值，$0\leq a\leq \lfloor\frac{n-1}{2}\rfloor$。
是不是感觉可做了许多$\rm{.jpeg}$。
---
我们考虑如何快速算出 $z_a$。
- 在此之前，我们先想想：如果我们确定了 $x,y$，那么 $i,j,k$ 共有多少种取值。
有一点是可以肯定的：一旦 $x,y$ 被确定，那么 $i,j,k$ 中的**任意**两个数也就相应地确定下来了。
不妨设确定的两个数为 $j,k$，用含 $k,x,y$ 的柿子表示 $i$ 就是 $i=k+x+y$。
给定 $i\leq n,k\ge 1$ 的限制，得 $1\leq k\le n-x-y$。
也就是说，如果 $x,y$ 确定，那么相应的 $i,j,k$ 共有 $(n-x-y)-1+1=n-x-y$ 种取值。
- 然后我们考虑当 $\min(x,y)=a$ 时 $x,y$ 有哪些情况。
易想到为 $x=a,y\in[a,n-a-1]$ 或 $x\in[a,n-a-1],y=a$。
注意到 $x=a,y=a$ 被包含在两种情况中，计算时要减去。
很容易就可以算出 $x=a,y\in[a,n-a-1]$ 时 $i,j,k$ 共有多少种取值：
$$\sum_{b=a}^{n-a-1}n-a-b$$
化简得
$$\sum_{b=1}^{n-2a}b$$
带入等差数列求和公式，即
$$\frac{(1+n-2a)\times(n-2a)}{2}$$
反之亦然，即 $x,y$ 交换顺序后取值数不变，所以
$$z_a=2\times\frac{(1+n-2a)\times(n-2a)}{2}-(n-2a)$$
注意最后那个 $n-2a$ 是 $x=a,y=a$ 时重复计算的情况数。
上式仍能化简，得
$$\begin{aligned}z_a&=(1+n-2a)\times(n-2a)-(n-2a)\\&=(n-2a)+(n-2a)\times(n-2a)-(n-2a)\\&=(n-2a)^2\end{aligned}$$
于是我们就能光速求出 $z_a$。
---
将 $z_a$ 的公式带入原式，得
$$\sum_{a=0}^{\lfloor\frac{n-1}{2}\rfloor}a!\times (n-2a)^2$$
这样我们就可以 $\Theta(n)$ 求答案，可过 $\rm{Subtask\ 2}$。
---
这样好像还是不够快，怎么办？！
好像没有能够 $\Theta(1)$ 计算的方法啊$\rm{.png}$。
不慌，当然有：
考虑把上式用完全平方公式拆开来，得
$$\sum_{a=0}^{\lfloor\frac{n-1}{2}\rfloor}a!\times n^2-a!\times4a\times n+a!\times 4a^2$$
然后 $\Theta(n)$ 预处理出 $a!$，$a!\times 4a$，$a!\times 4a^2$ 的前缀和，就可以做到 $\Theta(1)$ 计算了，可过 $\rm{Subtask\ 3}$。
---
附上不长的代码。
```
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,mod=10086001;
long long frc[N],pre1[N],pre2[N],pre3[N],ans[N],n,t,q,u;
int main(){
frc[0]=pre1[0]=1;
for(int i=1;i<N>>1;i++){
frc[i]=(frc[i-1]*i)%mod;
pre1[i]=(pre1[i-1]+frc[i])%mod;
pre2[i]=(pre2[i-1]+frc[i]*4*i)%mod;
pre3[i]=(pre3[i-1]+frc[i]*4*i%mod*i)%mod;
}//预处理部分
scanf("%lld",&t);
while(t--){
scanf("%lld",&q);
u=(q-1)/2;
printf("%lld\n",((pre1[u]*q%mod*q-pre2[u]*q+pre3[u])%mod+mod)%mod);
}//计算询问部分
return 0;
}
```
如果发现笔误或学术上的错误，请在右侧评论区指出或直接私信我 qwq。
完结撒花 ~ 码字不易，点个赞呗 awa。
$\rm{Upd\ on\ 2020.2.2}$ 修改一处笔误。