結果
問題 |
No.1417 100の倍数かつ正整数(2)
|
ユーザー |
![]() |
提出日時 | 2021-03-05 22:03:55 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 155 ms / 3,000 ms |
コード長 | 2,056 bytes |
コンパイル時間 | 279 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 80,472 KB |
最終ジャッジ日時 | 2024-10-07 01:58:51 |
合計ジャッジ時間 | 4,122 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
import sys input = sys.stdin.readline S = list(map(int, list(input())[: -1])) mod = 10 ** 9 + 7 ln = len(S) dp = [[0] * 9 for _ in range(ln + 1)] dp[1][0] = 1 dplim = [[0] * 9 for _ in range(ln + 1)] dplim[0][0] = 1 for i in range(ln): x = S[i] if i + 1 >= 2: dp[i + 1][0] += 1 for two in range(3): for five in range(3): j = two * 3 + five if x: if x % 2 == 0 and x % 4 != 0: dplim[i + 1][min(2, two + 1) * 3 + five] += dplim[i][j] dplim[i + 1][min(2, two + 1) * 3 + five] %= mod elif x % 4 == 0: dplim[i + 1][min(2, two + 2) * 3 + five] += dplim[i][j] dplim[i + 1][min(2, two + 2) * 3 + five] %= mod elif x % 5 == 0: dplim[i + 1][two * 3 + min(2, five + 1)] += dplim[i][j] dplim[i + 1][two * 3 + min(2, five + 1)] %= mod else: dplim[i + 1][j] += dplim[i][j] dplim[i + 1][j] %= mod for k in range(1, x): if k % 2 == 0 and k % 4 != 0: dp[i + 1][min(2, two + 1) * 3 + five] += dplim[i][j] dp[i + 1][min(2, two + 1) * 3 + five] %= mod elif k % 4 == 0: dp[i + 1][min(2, two + 2) * 3 + five] += dplim[i][j] dp[i + 1][min(2, two + 2) * 3 + five] %= mod elif k % 5 == 0: dp[i + 1][two * 3 + min(2, five + 1)] += dplim[i][j] dp[i + 1][two * 3 + min(2, five + 1)] %= mod else: dp[i + 1][j] += dplim[i][j] dp[i + 1][j] %= mod for k in range(1, 10): if k % 2 == 0 and k % 4 != 0: dp[i + 1][min(2, two + 1) * 3 + five] += dp[i][j] dp[i + 1][min(2, two + 1) * 3 + five] %= mod elif k % 4 == 0: dp[i + 1][min(2, two + 2) * 3 + five] += dp[i][j] dp[i + 1][min(2, two + 2) * 3 + five] %= mod elif k % 5 == 0: dp[i + 1][two * 3 + min(2, five + 1)] += dp[i][j] dp[i + 1][two * 3 + min(2, five + 1)] %= mod else: dp[i + 1][j] += dp[i][j] dp[i + 1][j] %= mod print((dp[-1][-1] + dplim[-1][-1]) % mod)