ABC248C

ABC248C の解説

atcoder.jp

解答コード

https://atcoder.jp/contests/abc248/submissions/31033351

問題

数列の和がK以下となるような数列が何通りあるか解く問題です．

解説

C問題にしては，かなーーり難しめな問題2次元DPの問題です．
概要図です．

ABC248C_overview

標準入力とMODを定義します．

MOD = 998244353
N, M, K = map(int, input().split())

dpの配列を定義します．
最初の項で取れる場合の数を定義します．

dp = [[0]*(K+1) for _ in range(N)]
dp[0][1: M+1] = [1]*M

順番に項を処理していきます．
第i項をjとしたときの合計が(j+k)となる場合の数を足していきます．
もし(j+k)が与えられたKを超えるようであれば，考える必要はないのでcontinueです．
MODの計算も忘れずにしましょう．

for i in range(1, N):
    for j in range(1, M+1):
        for k in range(1, K+1):
            if k + j > K:
                continue
            dp[i][k+j] += dp[i-1][k]
            dp[i][k+j] %= MOD

最後にK以下の場合をすべて合計して出力します．

ans = sum(dp[-1]) % MOD
print(ans)

以上，ABC248Cの解説でした．

＜参考解説リンク＞