AtCoder Beginner Contest 220 D - FG operation【Python】
https://atcoder.jp/contests/abc220/tasks/abc220_d
AtCoder ProblemsのRecommendationでDifficulty: 664、Solve Probability:
40%でした。
動的計画法で解くことができました。 MODを見逃しておりWA、またMODの値が10 ** 9 + 7ではなく998244353であることにも気づかずWAとなってしまったので注意したいです。
MOD = 998244353 N = int(input()) A = list(map(int, input().split())) dp = [[0] * 10 for _ in range(N)] dp[0][A[0]] = 1 for i in range(1, N): for j in range(10): if dp[i-1][j] > 0: a = A[i] count = dp[i-1][j] dp[i][a * j % 10] += count % MOD dp[i][(a + j) % 10] += count % MOD ans = dp[N-1] for i in range(10): print(ans[i] % MOD)