P12518「MSTOI-R1」Easy question 题解

· · 题解

题目链接

由于我们在操作时需要用到区间和以及区间次方和，而 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;
}