题解：P12518 「MSTOI-R1」Easy question

· · 题解

观察数据范围可以发现暴力肯定过不了，所以考虑预处理优化。

前缀次方和

定义二维数组

S[j][i]\;=\;\sum_{t=1}^i a_t^j \bmod M,\quad j=1,2,\dots,20,\;i=1,2,\dots,n。

预处理时对每个位置 i 计算

p = a_i \bmod M,\quad S[1][i]=\bigl(S[1][i-1]+p\bigr)\bmod M,

然后递推

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) 获得：

\sum_{t=l}^r a_t^j =\bigl(S[j][r]-S[j][l-1]+M\bigr)\bmod M。

对于操作 1

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

对于操作 2

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

对于操作 3

我们考虑将式子化简。

令区间长度 m=r-l+1，区间一次和

U=\sum_{i=l}^r a_i,\quad V=\sum_{i=l}^r a_i^2。

记 \bar a = U/m。原式 =

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。

因此

\text{ans} =\bigl(m\cdot (S[2][r]-S[2][l-1]) - (S[1][r]-S[1][l-1])^2 \;+\;M\bigr)\bmod M。 
#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;
}