Submission #64345131

---

Source Code Expand

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    Mod = 998244353

    binom = [[0] * (K + 1) for _ in range(K + 1)]
    for n in range(K + 1):
        binom[n][0] = 1
        for r in range(1, K + 1):
            binom[n][r] = binom[n - 1][r - 1] + binom[n - 1][r]

    dp = [0] * (K + 1)
    dp_prev = [0] * (K + 1)
    power = [1] * (K + 1)
    ans = 0
    for p in range(N):
        dp_prev, dp = dp, dp_prev

        for k in range(K + 1):
            if k == 0:
                dp[k] = 1
            else:
                dp[k] = power[k] = A[p] * power[k - 1] % Mod

        for k in range(K + 1):
            dp[k] += sum((binom[k][m] * power[m]) % Mod * dp_prev[k - m] % Mod for m in range(k + 1))

        ans += dp[K]

    return ans % Mod

#==================================================
print(solve())

Submission Info

Judge Result