题解：AT_abc399_f [ABC399F] Range Power Sum

· · 题解

题目链接

这次的F题有点难度，估计可以评个绿题吧。

思路

此题可以用DP+二项式定理解决。

我们设 dp_{r,k} = \sum^r_{l = 1} (\sum^r_{i = l} A_i)^k ，然后我们考虑转移。

dp_{r + 1, k} = \sum^{r + 1}_{i = l} (\sum^{r + 1}_{i = l} A_i)^k \space\space\space\space\space\space\space\space \space\space\space\space\space = A_{r + 1}^k + \sum^r_{i = 1} (\sum^r_{i = 1} A_i + A_{r + 1}) ^ k

然后根据二项式定理 (x + y) ^ k = \sum^k_{j = 1}\binom{k}{j}x^jy^{k - j} :

如果我们将 \sum^r_{i = 1} A_i 看做 x ， A_{r + 1} 看做 y 。

那么原式就变成了：

\space\space\space\space A_{r + 1}^k + \sum^r_{l = 1} \sum^r_{i = l} \binom{k}{j} (\sum^k_{j = 1}A_i) ^ j A_{r + 1} ^ {k - j} =A_{r + 1}^k + \sum^k_{j = 1} \binom{k}{j} \sum^r_{l = 1} (\sum^r_{i = l} A_i) ^ j A_{r + 1} ^ {k - j}

然后观察一下中间的这个式子 \sum^r_{l = 1} (\sum^r_{i = l} A_i) ^ j ， 这不就是 dp_{r,j} 吗！

所以最后的转移方程就长这样：

dp_{i + 1,j} = A_{r + 1}^k + \sum^k_{j = 1} \binom{k}{j} dp_{r, j}

最终的结果就是 \sum^n_{i = 1} dp_{i, k} 。

代码

#include <bits/stdc++.h>

#define endl '\n'
#define int long long

const int Mod = 998244353;

signed main (void) {

    std :: ios :: sync_with_stdio (false);
    std :: cin.tie (nullptr);
    std :: cout.tie (nullptr);

    int N, K;

    std :: cin >> N >> K;

    std :: vector <int> A (N + 1);

    for (int i = 1; i <= N; ++ i) {

        std :: cin >> A[i];
    }

    std :: vector <std :: vector <int> > F (K + 1);

    F[0].resize (K + 1);
    F[0][0] = 1;

    for (int i = 1; i <= K; ++ i) {

        F[i].resize (K + 1);

        F[i][0] = F[i][i] = 1;

        for (int j = 1; j < i; ++ j) {

            F[i][j] = F[i - 1][j] + F[i - 1][j - 1] % Mod;
        }
    } 

    std :: vector <int> Result (K + 1), Presult (K + 1), Comb (K + 1);

    int Answer = 0;

    for (int i = 1; i <= N; ++ i) {

        Comb[0] = 1;

        for (int j = 1; j <= K; ++ j) {

            Comb[j] = Comb[j - 1] * A[i] % Mod;
        }

        for (int k = 0; k <= K; ++ k) {

            Result[k] = Comb[k];

            for (int j = 0; j <= k; ++ j) {

                Result[k] = (Result[k] + Presult[j] * F[k][j] % Mod * Comb[k - j]) % Mod;
            }
        }

        Answer += Result[K];
        Answer %= Mod;

        Presult = Result;
    }

    std :: cout << Answer << endl;

    return 0;
}

完结撒花🎉🎉🎉