自动搬运

查看原文

来自洛谷，原作者为

	MinimumSpanningTree **

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

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

以下是正文

---

题目链接

由于我们在操作时需要用到区间和以及区间次方和，而 $k$ 最大只有 $20$，所以完全可以直接开一个数组维护次方和。定义 $s_{i,j}$ 表示 $\sum\limits_{k=1}^{i}a^j$。

对于操作 1，直接输出预处理的一次方区间和 $s_{r,1}-s_{l-1,1}$。

对于操作 2，直接输出预处理的 $k$ 次方和 $s_{r,k}-s_{l-1,k}$。

对于操作 3，我们考虑将式子拆开。

$$\begin{aligned} {}&(r-l+1) \sum_{i=l}^r\left(a_i-\overline a\right)^2&\\ =&(r-l+1)\sum_{i=l}^{r}{a_i}^2+\overline a^2-2a_i\overline a&\\ =&(r-l+1)[(\sum_{i=l}^r{a_i}^2)+(r-l+1)\overline a^2-2\overline a(\sum_{i=l}^ra_i)]&\\ =&(r-l+1)[(\sum_{i=l}^r{a_i}^2)+(\sum_{i=l}^ra_i)\overline a-2\overline a(\sum_{i=l}^ra_i)]&\\ =&(r-l+1)[(\sum_{i=l}^r{a_i}^2)-\overline a(\sum_{i=l}^ra_i)]&\\ =&(r-l+1)(\sum_{i=l}^r{a_i}^2)-(r-l+1)\overline a(\sum_{i=l}^ra_i)&\\ =&(r-l+1)(\sum_{i=l}^r{a_i}^2)-(\sum_{i=l}^ra_i)^2 \end{aligned} $$

再使用预处理的 $s$ 数组，可以得到 $ans=(r-l+1)(s_{r,2}-s_{l-1,2})-(s_{r,1}-s_{l-1,1})^2$。

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N=1e6+100,K=25;
const ll MOD=998244353;
int n,q,op;
ll a[N],s[N][K],u,v,w,ans;
int main() 
{
	//freopen("data1.in","r",stdin); 
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) 
	{
		scanf("%lld",&a[i]);
		s[i][0]=1;
		for(int j=1;j<=20;j++) s[i][j]=s[i][j-1]*a[i]%MOD;
		for(int j=1;j<=20;j++) 
		{
			s[i][j]=(s[i][j]+s[i-1][j])%MOD; 
			//printf("%d %d %lld\n",i,j,s[i][j]);
		}
	}
	while(q--)
	{
		scanf("%d%lld%lld",&op,&u,&v);
		if(op==1) ans=(s[v][1]+MOD-s[u-1][1])%MOD;
		else if(op==2)
		{
			scanf("%d",&w);
			ans=(s[v][w]+MOD-s[u-1][w])%MOD;
		}
		else ans=((v-u+1)*(s[v][2]+MOD-s[u-1][2])%MOD+MOD-(s[v][1]+MOD-s[u-1][1])%MOD*(s[v][1]+MOD-s[u-1][1])%MOD)%MOD;
		printf("%lld\n",ans);
	} 
	return 0;
}