题解：AT_abc399_f [ABC399F] Range Power Sum

· · 题解

题目传送门

\mathtt{Solution}

简单题。

观察这个式子的形式，发现它可以用二项式定理拆开。

记 s_i=\sum\limits_{j=1}^{i}a_i，其中 s_0=0，那么原式可表示为： \displaystyle\sum_{1\leq\ l\leq\ r\leq\ n}(s_r-s_{l-1})^k 。

由于 k 不超过 10，那么我们可以用二项式定理展开。

(s_r-s_{l-1})^k=\displaystyle\ \sum_{i=0}^{k}C_k^i\ s_r^i\ s_{l-1}^{k-i}\ (-1)^i

由于 C_k^i\ s_r^i\ (-1)^i 可以提出来，那么只需要枚举 r，然后前缀和优化就可以了。

赛时代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
    int s = 0, f = 1;char ch = getchar();
    while(!isdigit(ch)){if(ch == '-')f = -1;ch = getchar();}
    while(isdigit(ch)){s = s * 10 + ch - '0';ch = getchar();}
    return s * f;
}
void write(int x){
    if(x < 0){putchar('-'); x = -x;}
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
const int MAXN = 2e5 + 5, MOD = 998244353;
int n, k, ans, a[MAXN], s[MAXN], fac[MAXN], inv[MAXN], sum[MAXN];
int fpow(int a, int b){
    int res = 1;
    while(b){
        if(b & 1ll)res = res * a % MOD;
        a = a * a % MOD;
        b = b >>= 1ll;
    }
    return res;
}
int C(int x, int y){
    if(x < y)return 0;
    return fac[x] * inv[y] % MOD * inv[x - y] % MOD;
}
signed main(){
    n = read(), k = read();
    for(int i = 1;i <= n;i ++)a[i] = read(), s[i] = (s[i - 1] + a[i]) % MOD;
    fac[0] = 1;
    for(int i = 1;i <= 2e5;i ++)fac[i] = fac[i - 1] * i % MOD;
    inv[200000] = fpow(fac[200000], MOD - 2);
    for(int i = 2e5 - 1;i >= 0;i --)inv[i] = inv[i + 1] * (i + 1) % MOD;
    for(int i = 0;i <= n;i ++){
        for(int j = 0;j <= k;j ++){
            ans += C(k, j) * sum[j] % MOD * fpow(-1, j) % MOD * fpow(s[i], k - j) % MOD;
            ans %= MOD;
            ans += MOD;
            ans %= MOD;
            sum[j] += fpow(s[i], j), sum[j] %= MOD;
        }
    }
    printf("%lld\n", ans);
    return 0;
}