AT_abc399_f

· · 题解

感觉赛时脑梗了

记s_i = \sum\limits_{1 \le j \le i} a_j

\sum\limits_{i > j \ge 1}(s_i - s_j) ^ k = \sum\limits_{i > j \ge 1}\sum\limits_{0\le l \le k} \binom{k}{l} s_i^l s_j^{k - l}(-1)^{k - l} = \sum\limits_{0\le l \le k} \binom{k}{l}(-1)^{k-l}s_i^l \sum\limits_{1\le j < i}s_j^{k - l}

计算时维护\sum\limits_{1 \le j < i} s_j ^ {k - l}

最后再加上\sum s_i^k即可

code:

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int maxn = 2e5 + 5, mod = 998244353;
int sum[maxn], val[15], n, k;
int c[15][15];
void init() {
    c[0][0] = 1;
    for (int i = 1; i <= 10; ++i) {
        for (int j = 0; j <= 10; ++j) {
            c[i][j] = c[i - 1][j];
            if (j) c[i][j] += c[i - 1][j - 1];
            c[i][j] %= mod;
        }
    }
}
int qpow(int a, int b) {
    int res = 1;
    for (int t = a; b; b >>= 1, t = (t * t) % mod) {
        if (b & 1) res = (res * t) % mod;
    }
    return res;
}
int add(int x, int y) {
    // return x + y;
    return ((x + y) % mod + mod) % mod;
}
signed main() {
    cin >> n >> k;
    init();
    for (int i = 1; i <= n; ++i) {
        int x; cin >> x;
        sum[i] = add(sum[i - 1], x);
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int l = 0; l <= k; ++l) {
            int cur = val[k - l];
            int f = (c[k][l] * ((k - l) & 1 ? -1 : 1) + mod) % mod;
            ans = add(ans, f * qpow(sum[i], l) % mod * cur % mod);
        }
        for (int l = 0; l <= k; ++l) {
            val[l] = add(val[l], qpow(sum[i], l));
        }
    }
    for (int i = 1; i <= n; ++i) {
        ans = add(ans, qpow(sum[i], k));
    }
    cout << ans << endl;
    return 0;
}