ABC248 C - Dice Sum
https://atcoder.jp/contests/abc248/tasks/abc248_c
提出
code: python
import itertools
n, m, k = map(int, input().split())
# 2 3 4
# A(A1, A2) 1 <= A1, A2 <= 3
# TODO: 探索を打ち切る
# TODO: itertools.product 使わない
ans = 0
for p in itertools.product(i for i in range(1, m+1), repeat=n):
if (sum(p) <= k):
ans += 1
print(ans % 998244353)
解答
code: python
n, m, K = map(int, input().split())
# 2 3 4
# A(A1, A2) 1 <= A1, A2 <= 3
MOD = 998244353
# dpij : 数列の i 番目まで決めて、総和が j であるものの数
# dpN1+dpN2+⋯+dpNKを求めたい
dp = [0 * (K + 1) for _ in range(n + 1)]
# dp00=1 : 数列の 0 番目まで決めて、総和が 0
dp00 = 1
#『i番目 Aiまで決めて、総和が j の数列』から、i+1番目の要素 Ai+1 を決めたときの遷移を考える。
# Ai+1 を 1 以上 M 以下の整数 k にすると、次の状態は『 i+1 番目 Ai+1 まで決めて、総和が j+k の数列』になる。
for i in range(n):
for j in range(K): # K以上はいらない
for k in range(1, m + 1): # Ai+1の数
if j + k > K: # K以上はいらない
break
dpi + 1j + k += dpij # 数列の i 番目まで決めて、総和が j であるものの数
dpi + 1j + k %= MOD
print(dp)
# print(i, j, k) print(dp)
# 0 0 1 1, 0, 0, 0, 0], 0, 1, 0, 0, 0, [0, 0, 0, 0, 0
# 0 0 2 1, 0, 0, 0, 0], 0, 1, 1, 0, 0, [0, 0, 0, 0, 0
# 0 0 3 1, 0, 0, 0, 0], 0, 1, 1, 1, 0, [0, 0, 0, 0, 0
# 0 1 1 1, 0, 0, 0, 0], 0, 1, 1, 1, 0, [0, 0, 0, 0, 0 # Ai+1=1で総和は2にならない
# 0 1 2 1, 0, 0, 0, 0], 0, 1, 1, 1, 0, [0, 0, 0, 0, 0
# 0 1 3 1, 0, 0, 0, 0], 0, 1, 1, 1, 0, [0, 0, 0, 0, 0
# 0 2 1 1, 0, 0, 0, 0], 0, 1, 1, 1, 0, [0, 0, 0, 0, 0
# 0 2 2 1, 0, 0, 0, 0], 0, 1, 1, 1, 0, [0, 0, 0, 0, 0
# 0 3 1 1, 0, 0, 0, 0], 0, 1, 1, 1, 0, [0, 0, 0, 0, 0
# 1 0 1 1, 0, 0, 0, 0], 0, 1, 1, 1, 0, [0, 0, 0, 0, 0
# 1 0 2 1, 0, 0, 0, 0], 0, 1, 1, 1, 0, [0, 0, 0, 0, 0
# 1 0 3 1, 0, 0, 0, 0], 0, 1, 1, 1, 0, [0, 0, 0, 0, 0
# 1 1 1 1, 0, 0, 0, 0], 0, 1, 1, 1, 0, [0, 0, 1, 0, 0
# 1 1 2 1, 0, 0, 0, 0], 0, 1, 1, 1, 0, [0, 0, 1, 1, 0
# 1 1 3 1, 0, 0, 0, 0], 0, 1, 1, 1, 0, [0, 0, 1, 1, 1
# 1 2 1 1, 0, 0, 0, 0], 0, 1, 1, 1, 0, [0, 0, 1, 2, 1
# 1 2 2 1, 0, 0, 0, 0], 0, 1, 1, 1, 0, [0, 0, 1, 2, 2
# 1 3 1 1, 0, 0, 0, 0], 0, 1, 1, 1, 0, [0, 0, 1, 2, 3
# print(dp)
# 1, 0, 0, 0, 0], 0, 1, 1, 1, 0, [0, 0, 1, 2, 3
print(sum(dp-1) % MOD)
テーマ
#dp
メモ
【AtCoder解説】PythonでABC248のA,B,C,D,E,F問題を制する!