AT_abc399_f [ABC399F] Range Power Sum

· · 题解

Content

求：

\sum_{ l = 1 }^n \sum_{ r = l }^ n ( \sum_{ i = l }^r a_i )^K \bmod 998244353

Solution

显然需要用到前缀和：

\sum_{ l = 1 }^n \sum_{ r = l }^ n ( sum_r - sum_{l-1} )^K

用二项式定理展开后可得：

\sum_{ k = 0 }^K \sum_{ l = 1 }^n \sum_{ r = l }^ n C^k_K \times sum_r^k \times ( -1 )^{ K - k } \times sum_{ l - 1 }^{ K - k }

再用前缀和（倒着跑一遍，将 r 优化掉）优化后便可以过了：

\sum_{ k = 0 }^K \sum_{ l = 1 }^ n C^k_K \times sum_l^k \times Sum_{ l + 1 , K - k } \times ( -1 )^k

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
const int mod=998244353;
int n,k,ans;
int a[N],sum[N];
int cnt[N][15],C[15][15];
int Pow(int a,int b){
    int cnt=a,ans=1;
    while(b){
        if(b&1)
            ans=ans*cnt%mod;
        cnt=cnt*cnt%mod;
        b>>=1; 
    }
    return ans;
}
void init(){
    C[0][0]=1;
    for(int i=1;i<=10;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++)
            C[i][j]=C[i-1][j]+C[i-1][j-1];
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    init();
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=(sum[i-1]+a[i])%mod;
    }
    for(int i=n;i>=1;i--)
        for(int j=0;j<=10;j++)
            cnt[i][j]=((cnt[i+1][j]+Pow(sum[i],j))%mod+mod);
    for(int i=0;i<n;i++)
        for(int j=0;j<=k;j++)
            ans=((ans+C[k][j]*Pow(sum[i],k-j)%mod*cnt[i+1][j]*Pow(-1,j)%mod)%mod+mod)%mod;
    if(k&1)
        ans=mod-ans;
    cout<<(ans%mod+mod)%mod;
    return 0;
}