結果

問題 No.1417 100の倍数かつ正整数(2)
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0