結果
問題 | No.1417 100の倍数かつ正整数(2) |
ユーザー |
![]() |
提出日時 | 2022-08-20 02:21:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,496 ms / 3,000 ms |
コード長 | 987 bytes |
コンパイル時間 | 685 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 114,688 KB |
最終ジャッジ日時 | 2024-10-08 14:57:03 |
合計ジャッジ時間 | 11,910 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
S = list(input()) N = len(S) mod = 10 ** 9 + 7 dp = [[[[0] * 100 for i in range(2)] for j in range(2)] for k in range(N + 1)] dp[0][0][0][1] = 1 for i in range(N): n = int(S[i]) for j in range(2): for k in range(100): for m in range(2): for d in range(10): ni = i + 1 nj = 1 nk = (k * d)%100 nm = 1 if j == 0 and d > n: continue if j == 0 and d == n: nj = 0 if d == 0: if m == 0: nk = 1 nm = 0 else: continue dp[ni][nj][nm][nk] += dp[i][j][m][k] dp[ni][nj][nm][nk] %= mod ans = 0 for i in range(2): for j in range(2): ans += dp[N][i][j][0] ans %= mod print(ans)