結果

問題 No.1417 100の倍数かつ正整数(2)
ユーザー lam6er
提出日時 2025-03-26 15:48:51
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,502 bytes
コンパイル時間 369 ms
コンパイル使用メモリ 82,300 KB
実行使用メモリ 78,264 KB
最終ジャッジ日時 2025-03-26 15:49:49
合計ジャッジ時間 4,514 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

s = input().strip()
digits = list(map(int, s))
n = len(digits)

# Precompute the number of 2s and 5s in each digit (0-9)
factors = [
    (0, 0),  # 0
    (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
]

# Initialize DP table. The state is [tight][leading_zero][c2][c5]
dp = [[[[0] * 3 for _ in range(3)] for __ in range(2)] for ___ in range(2)]
dp[1][1][0][0] = 1  # Start with tight=1, leading_zero=1, c2=0, c5=0

for i in range(n):
    next_dp = [[[[0] * 3 for _ in range(3)] for __ in range(2)] for ___ in range(2)]
    for tight in [0, 1]:
        for leading_zero in [0, 1]:
            for c2 in range(3):
                for c5 in range(3):
                    cnt = dp[tight][leading_zero][c2][c5]
                    if cnt == 0:
                        continue
                    upper = digits[i] if tight else 9
                    for d in range(0, upper + 1):
                        new_tight = tight and (d == upper)
                        new_leading_zero = leading_zero and (d == 0)
                        if not leading_zero and d == 0:
                            continue  # Non-leading zero state cannot have 0
                        if new_leading_zero:
                            new_c2 = c2
                            new_c5 = c5
                        else:
                            a, b = factors[d]
                            new_c2 = min(c2 + a, 2)
                            new_c5 = min(c5 + b, 2)
                        next_dp[new_tight][new_leading_zero][new_c2][new_c5] += cnt
                        next_dp[new_tight][new_leading_zero][new_c2][new_c5] %= MOD
    dp = next_dp

# Calculate the answer from the DP states
ans = 0
for tight in [0, 1]:
    for leading_zero in [0, 1]:
        for c2 in range(3):
            for c5 in range(3):
                if leading_zero == 0 and c2 >= 2 and c5 >= 2:
                    ans = (ans + dp[tight][leading_zero][c2][c5]) % MOD

# Check if N itself is valid
has_zero = False
total_2 = 0
total_5 = 0
leading_zero = True
for d in digits:
    if leading_zero:
        if d == 0:
            continue
        else:
            leading_zero = False
    else:
        if d == 0:
            has_zero = True
            break
    a, b = factors[d]
    total_2 += a
    total_5 += b

if not has_zero and not leading_zero and total_2 >= 2 and total_5 >= 2:
    ans = (ans + 1) % MOD

print(ans)
0