結果

問題 No.315 世界のなんとか3.5
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:24:01
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,386 bytes
コンパイル時間 160 ms
コンパイル使用メモリ 82,060 KB
実行使用メモリ 177,280 KB
最終ジャッジ日時 2025-04-16 00:25:09
合計ジャッジ時間 4,929 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def subtract_one(s):
    s_list = list(s)
    i = len(s_list) - 1
    while i >= 0 and s_list[i] == '0':
        s_list[i] = '9'
        i -= 1
    if i == -1:
        return '0'
    s_list[i] = str(int(s_list[i]) - 1)
    if s_list[0] == '0' and len(s_list) > 1:
        return ''.join(s_list[1:])
    return ''.join(s_list)

def count(s, P):
    n = len(s)
    dp = [{} for _ in range(n + 1)]
    dp[0] = { (True, True, 0, False, 0): 1 }
    
    for pos in range(n):
        current_digit = int(s[pos])
        for state in dp[pos]:
            tight, leading_zero, sum_mod3, has_three, mod_p = state
            count_val = dp[pos][state]
            
            max_d = current_digit if tight else 9
            for d in range(0, max_d + 1):
                new_tight = tight and (d == max_d)
                new_leading_zero = leading_zero and (d == 0)
                
                new_sum_mod3 = sum_mod3
                new_has_three = has_three
                new_mod_p = mod_p
                
                if not leading_zero:
                    new_sum_mod3 = (sum_mod3 + d) % 3
                    new_has_three = has_three or (d == 3)
                    new_mod_p = (mod_p * 10 + d) % P
                else:
                    if d != 0:
                        new_leading_zero = False
                        new_sum_mod3 = d % 3
                        new_has_three = (d == 3)
                        new_mod_p = d % P
                    else:
                        new_sum_mod3 = 0
                        new_has_three = False
                        new_mod_p = 0
                
                key = (new_tight, new_leading_zero, new_sum_mod3, new_has_three, new_mod_p)
                if key not in dp[pos + 1]:
                    dp[pos + 1][key] = 0
                dp[pos + 1][key] = (dp[pos + 1][key] + count_val) % MOD
    
    total = 0
    for state in dp[n]:
        tight, leading_zero, sum_mod3, has_three, mod_p = state
        if leading_zero:
            continue
        if (sum_mod3 == 0) or has_three:
            if mod_p != 0:
                total = (total + dp[n][state]) % MOD
    return total

A, B, P = input().split()
P = int(P)

A_minus_1 = subtract_one(A)
len_B = len(B)
A_minus_1 = A_minus_1.zfill(len_B)

count_B = count(B, P)
count_A = count(A_minus_1, P)
ans = (count_B - count_A) % MOD
print(ans)
0