自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:16:49，当前版本为作者最后更新于2020-02-01 23:23:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

写篇小学生也能看懂的题解，不需要找规律。

虽然看起来有一丢丢麻烦，但如果你认真读一定能看懂 ~

$\rm{Subtask\ 1}$ 无脑 $\Theta(n)$ 预处理阶乘，再 $\Theta(n^4)$ 预处理 $n\in[1,10^2]$ 的所有答案最后 $\Theta(1)$ 回答询问即可。

---

首先化简一下题目给出的柿子

$$\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}$ 修改一处笔误。