ABC399F - Range Power Sum

問題

リンク 長さ$N$の整数列$A$と$K$が与えられるので、以下の式ををmod 998で求めて下さい。

解法

とりあえず与えられた式を理解しやすいように書き換えると、

という３重シグマの形になる。が、一番内側のシグマについては区間和を表しているので、累積和を用いることで容易に外せる。数列$S$を$S_0 = 0$, $S_i = A_1 + \cdots + A_i$とすると、

となる。どう考えても$K$乗の部分が厄介なので、二項展開¹を用いてこれを外すと、以下のようになる。

3重シグマとなったが、これらを交換しても答えは変わらない。また、シグマから外側に出せるものは出してしまうことにする。これらを適用すると、式は以下のように変形できる。

ここで、$\sum_{r=l}^N {S_r}^{K-p}$はの累積和を前計算しておくことによって、各に対してで計算ができる。よって全体でで解くことが可能で、この問題の制約下では十分高速になる。

提出

提出(C++23, 45ms)

using mint = modint998244353;
mint ncr(int n, int r) {
    mint res = 1;
    rep(i,r) {
        res *= (n-i)