自动搬运

查看原文

来自洛谷，原作者为

	LimityZetta "不是想要更好的未来吗"

搬运于2025-08-24 23:14:13，当前版本为作者最后更新于2025-04-22 19:26:58，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

这题太冷了，也是水一篇题解。

P12273

题解

对于这类数学题，我们要拿出我们的传统艺能：推规律。

以下我们约定：

$f_i^{(m)}$ 为原序列的 $m$ 次异位和数组的第 $i$ 项， $S$ 为原序列的和，即 $\sum_{i=1}^{n}A_i$。

不难推出：

$$\begin{aligned} f_i^{(1)}&=S-A_i\\ f_i^{(2)}&=S \cdot n - (\sum_{i=1}^{n}A_i)-(S-A_i)\\ &=(n-1)S - S+A_i\\ \end{aligned} $$

等等的式子，只需要对上一次的异位和数组求和，再减去上一次异位和数组的对应一项，就都可以推出来。

事实上，通过前四次推导：

$$\begin{aligned} f_i^{(1)}&=S-A_i\\ f_i^{(2)}&=(n-1)S - S+A_i\\ f_i^{(3)}&=(n-1)^2S-(n-2)S-A_i\\ f_i^{(4)}&=(n-1)^3S-(n^2-3n+3)S+A_i\\ \end{aligned} $$

我们能大概得出一个规律：

$$f_i^{(m)}=(n-1)^{m-1}S-\frac{(n-1)^{m-1}+(-1)^m}{n}\times S+(-1)^m \times A_i $$

有了这个式子，剩下的只有取模了。

我们不妨把式子拆成前、中、后三部分：

最后一项 $(-1)^m \times A_i$ 直接取模即可。

前面一项 $(n-1)^{m-1}S$ 也不难，在快速幂里取模即可。

剩下一项有点麻烦，需要先对分母 $n$ 求模逆 ，再乘以分子再取模。

由于 $998244353$ 是质数，这里采用的费马小定理求模逆。

最后分段取模后，$ans$ 一定要先加一个模数再取模，不然可能对负数取模，会出错。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
#define mod 998244353
const int mxn=1e5+2;
int n,a[mxn],q;
long long Pow(long long a,long long b,long long p){
	long long base=a,ans=1;
	while(b){
		if(b&1){
			ans*=base;
			ans%=p;
		}
		base*=base,base%=p;
		b>>=1;
	}
	return ans%p;
}
long long s;
int main() {
	scanf("%d",&n);
	long long inv=Pow(n,mod-2,mod);//模逆，这里预计算
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		s+=a[i];
	}
	s%=mod;//sum
	scanf("%d",&q);
	while(q--){
		long long k,x;
		scanf("%lld%lld",&k,&x);
		//(-1)^k
		int sign=(k&1)?-1:1;
		
		long long y=Pow(n-1,k-1,mod);//(n-1)^(k-1)
		long long frac=((y+sign)%mod*inv%mod)%mod;//中间项的分数
		//ans
		long long ans=(s%mod*y)%mod;//前一项
		ans-=(frac*s%mod)%mod;//中间项
		ans+=sign*(a[x]%mod);//最后一项
		printf("%lld\n",(ans+mod*2)%mod);
	}
}