考え方
配るDPなら区間への遷移．貰うDPなら区間への遷移．よって，よくある累積和を取りながらのDP．
【類題】
回答例（配るDP & いもす法）
$K=0$の場合に注意．N, M, K = map(int, input().split()) mod = 998244353 dp = [[0] * (M + 1) for _ in range(N + 1)] dp[1] = [1] * (M + 1) for i in range(1, N): for j in range(1, M + 1): if K == 0: dp[i + 1][1] += dp[i][j] dp[i + 1][1] %= mod continue if j + K <= M: dp[i + 1][j + K] += dp[i][j] dp[i + 1][j + K] %= mod if 0 < j - K: dp[i + 1][1] += dp[i][j] dp[i + 1][1] %= mod if j - K + 1 <= M: dp[i + 1][j - K + 1] -= dp[i][j] dp[i + 1][j - K + 1] %= mod for j in range(1, M): dp[i + 1][j + 1] += dp[i + 1][j] dp[i + 1][j + 1] %= mod print(sum(dp[-1]) % mod)
