結果
問題 | No.1417 100の倍数かつ正整数(2) |
ユーザー |
![]() |
提出日時 | 2025-03-31 17:44:31 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 139 ms / 3,000 ms |
コード長 | 2,682 bytes |
コンパイル時間 | 188 ms |
コンパイル使用メモリ | 82,544 KB |
実行使用メモリ | 77,720 KB |
最終ジャッジ日時 | 2025-03-31 17:45:20 |
合計ジャッジ時間 | 3,901 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
mod = 10**9 + 7 digit_add = [ (0, 0), # index 0 (unused) (0, 0), # 1 (1, 0), # 2 (0, 0), # 3 (2, 0), # 4 (0, 1), # 5 (1, 0), # 6 (0, 0), # 7 (3, 0), # 8 (0, 0), # 9 ] N_str = input().strip() len_N = len(N_str) n_digits = [int(c) for c in N_str] # Part 1: Calculate the count of valid numbers for lengths 1 to len_N-1 part1 = 0 if len_N > 1: current_dp = [[0] * 3 for _ in range(3)] for L in range(1, len_N): new_dp = [[0] * 3 for _ in range(3)] if L == 1: for d in range(1, 10): a2, a5 = digit_add[d] new_c2 = min(a2, 2) new_c5 = min(a5, 2) new_dp[new_c2][new_c5] = (new_dp[new_c2][new_c5] + 1) % mod else: for prev_c2 in range(3): for prev_c5 in range(3): cnt = current_dp[prev_c2][prev_c5] if cnt == 0: continue for d in range(1, 10): a2, a5 = digit_add[d] new_c2 = min(prev_c2 + a2, 2) new_c5 = min(prev_c5 + a5, 2) new_dp[new_c2][new_c5] = (new_dp[new_c2][new_c5] + cnt) % mod # Sum the valid states for current L total = 0 for c2 in [2]: for c5 in [2]: total = (total + new_dp[c2][c5]) % mod part1 = (part1 + total) % mod current_dp = new_dp # Part 2: Calculate the count of valid numbers of length len_N (up to N) part2_count = 0 if len_N >= 1: dp_prev = [[[0] * 3 for _ in range(3)] for _ in range(2)] dp_prev[1][0][0] = 1 # Initial state: tight=True, c2=0, c5=0, count=1 for pos in range(len_N): dp_next = [[[0] * 3 for _ in range(3)] for _ in range(2)] for tight in [0, 1]: for c2 in range(3): for c5 in range(3): cnt = dp_prev[tight][c2][c5] if cnt == 0: continue max_d = n_digits[pos] if tight else 9 for d in range(1, max_d + 1): new_tight = 1 if (tight and d == max_d) else 0 a2, a5 = digit_add[d] new_c2 = min(c2 + a2, 2) new_c5 = min(c5 + a5, 2) dp_next[new_tight][new_c2][new_c5] = (dp_next[new_tight][new_c2][new_c5] + cnt) % mod dp_prev = dp_next # Sum valid states after processing all digits for tight in [0, 1]: part2_count = (part2_count + dp_prev[tight][2][2]) % mod total = (part1 + part2_count) % mod print(total)