結果
問題 | 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 sysinput = sys.stdin.readlineS = list(map(int, list(input())[: -1]))mod = 10 ** 9 + 7ln = len(S)dp = [[0] * 9 for _ in range(ln + 1)]dp[1][0] = 1dplim = [[0] * 9 for _ in range(ln + 1)]dplim[0][0] = 1for i in range(ln):x = S[i]if i + 1 >= 2: dp[i + 1][0] += 1for two in range(3):for five in range(3):j = two * 3 + fiveif 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] %= modelif x % 4 == 0:dplim[i + 1][min(2, two + 2) * 3 + five] += dplim[i][j]dplim[i + 1][min(2, two + 2) * 3 + five] %= modelif x % 5 == 0:dplim[i + 1][two * 3 + min(2, five + 1)] += dplim[i][j]dplim[i + 1][two * 3 + min(2, five + 1)] %= modelse:dplim[i + 1][j] += dplim[i][j]dplim[i + 1][j] %= modfor 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] %= modelif k % 4 == 0:dp[i + 1][min(2, two + 2) * 3 + five] += dplim[i][j]dp[i + 1][min(2, two + 2) * 3 + five] %= modelif k % 5 == 0:dp[i + 1][two * 3 + min(2, five + 1)] += dplim[i][j]dp[i + 1][two * 3 + min(2, five + 1)] %= modelse:dp[i + 1][j] += dplim[i][j]dp[i + 1][j] %= modfor 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] %= modelif k % 4 == 0:dp[i + 1][min(2, two + 2) * 3 + five] += dp[i][j]dp[i + 1][min(2, two + 2) * 3 + five] %= modelif k % 5 == 0:dp[i + 1][two * 3 + min(2, five + 1)] += dp[i][j]dp[i + 1][two * 3 + min(2, five + 1)] %= modelse:dp[i + 1][j] += dp[i][j]dp[i + 1][j] %= modprint((dp[-1][-1] + dplim[-1][-1]) % mod)