专栏文章

题解：P12518 「MSTOI-R1」Easy question

ZZG10086
P12518题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip9z306
此快照首次捕获于
2025/12/03 08:34
3 个月前
此快照最后确认于
2025/12/03 08:34
3 个月前
查看原文
观察数据范围可以发现暴力肯定过不了，所以考虑预处理优化。

前缀次方和

定义二维数组
S[j][i]  =  ∑t=1iatj mod M,j=1,2,…,20,  i=1,2,…,n。 S[j][i]\;=\;\sum_{t=1}^i a_t^j \bmod M,\quad j=1,2,\dots,20,\;i=1,2,\dots,n。
预处理时对每个位置 ii 计算
p=ai mod M,S[1][i]=(S[1][i−1]+p) mod M, p = a_i \bmod M,\quad S[1][i]=\bigl(S[1][i-1]+p\bigr)\bmod M,
然后递推
p←(p×ai) mod M,S[j][i]=(S[j][i−1]+p) mod M,j=2…20。 p \leftarrow (p \times a_i)\bmod M,\quad S[j][i]=\bigl(S[j][i-1]+p\bigr)\bmod M,\quad j=2\dots20。
这样任意次方区间和都可 O(1)O(1) 获得：
∑t=lratj=(S[j][r]−S[j][l−1]+M) mod M。 \sum_{t=l}^r a_t^j =\bigl(S[j][r]-S[j][l-1]+M\bigr)\bmod M。

对于操作 1

直接输出预处理的一次方区间和 (S[1][r]−S[1][l−1]+M) mod M\bigl(S[1][r]-S[1][l-1]+M\bigr)\bmod M。

对于操作 2

直接输出预处理的 kk 次方区间和 (S[k][r]−S[k][l−1]+M) mod M\bigl(S[k][r]-S[k][l-1]+M\bigr)\bmod M。

对于操作 3

我们考虑将式子化简。
令区间长度 m=r−l+1m=r-l+1，区间一次和
U=∑i=lrai,V=∑i=lrai2。 U=\sum_{i=l}^r a_i,\quad V=\sum_{i=l}^r a_i^2。
记 aˉ=U/m\bar a = U/m。原式 ==
m∑i=lr(ai−aˉ)2=m(V−2aˉ U+maˉ2)=mV−2U2+U2=mV−U2。 m\sum_{i=l}^r(a_i-\bar a)^2 =m\Bigl(V -2\bar a\,U + m\bar a^2\Bigr) =mV -2U^2 + U^2 =mV - U^2。
因此
ans=(m⋅(S[2][r]−S[2][l−1])−(S[1][r]−S[1][l−1])2  +  M) mod M。 \text{ans} =\bigl(m\cdot (S[2][r]-S[2][l-1]) - (S[1][r]-S[1][l-1])^2 \;+\;M\bigr)\bmod M。 C
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=998244353;
ll s[25][1000010];
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		ll x;
		cin>>x;
		ll p=x%MOD;
		s[1][i]=(s[1][i-1]+p)%MOD;
		for(int j=2;j<=20;j++)
		{
			p=(p*x)%MOD;
			s[j][i]=(s[j][i-1]+p)%MOD;
		}
	}
	while(q--)
	{
		int op,l,r,k;
		cin>>op>>l>>r;
		if(op==1){
			ll ans=s[1][r]-s[1][l-1];
			if(ans<0) ans+=MOD;
			cout<<ans<<"\n";
		}else{
			if(op==2){
				cin>>k;
				ll ans=s[k][r]-s[k][l-1];
				if(ans<0) ans+=MOD;
				cout<<ans<<"\n";
			}
			else{
				ll m=r-l+1,U=s[1][r]-s[1][l-1],V=s[2][r]-s[2][l-1];
				if(U<0) U+=MOD;
            	if(V<0) V+=MOD;
				ll ans=(m*V%MOD-(U*U%MOD))%MOD;
				if(ans<0) ans+=MOD;
				cout<<ans<<"\n";
			}
		}
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...