結果

問題 No.315 世界のなんとか3.5
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:38:43
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,580 bytes
コンパイル時間 293 ms
コンパイル使用メモリ 82,040 KB
実行使用メモリ 86,880 KB
最終ジャッジ日時 2025-06-12 19:39:19
合計ジャッジ時間 8,920 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12 TLE * 3 -- * 21
権限があれば一括ダウンロードができます

ソースコード

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':
        if len(s_list) == 1:
            return '0'
        else:
            new_s = ''.join(s_list[1:]).lstrip('0')
            return new_s if new_s else '0'
    return ''.join(s_list)

def count_aho(s):
    n = len(s)
    dp = [[[0]*3 for _ in range(2)] for __ in range(2)]
    dp[1][0][0] = 1
    for i in range(n):
        curr_digit = int(s[i])
        new_dp = [[[0]*3 for _ in range(2)] for __ in range(2)]
        for tight in [0, 1]:
            for has3 in [0, 1]:
                for mod3 in [0, 1, 2]:
                    cnt = dp[tight][has3][mod3]
                    if cnt == 0:
                        continue
                    upper = curr_digit if tight else 9
                    for d in range(0, upper + 1):
                        new_tight = 1 if (tight and d == upper) else 0
                        new_has3 = 1 if (has3 or d == 3) else 0
                        new_mod3 = (mod3 + d) % 3
                        new_dp[new_tight][new_has3][new_mod3] = (
                            new_dp[new_tight][new_has3][new_mod3] + cnt
                        ) % MOD
        dp = new_dp
    total = 0
    for tight in [0, 1]:
        for has3 in [0, 1]:
            for mod3 in [0, 1, 2]:
                if has3 or mod3 == 0:
                    total = (total + dp[tight][has3][mod3]) % MOD
    return total

def count_aho_p(s, P):
    if P == 0:
        return 0
    n = len(s)
    dp = [[[[0]*P for _ in range(3)] for __ in range(2)] for ___ in range(2)]
    dp[1][0][0][0] = 1
    for i in range(n):
        curr_digit = int(s[i])
        new_dp = [[[[0]*P for _ in range(3)] for __ in range(2)] for ___ in range(2)]
        for tight in [0, 1]:
            for has3 in [0, 1]:
                for mod3 in [0, 1, 2]:
                    for modp in range(P):
                        cnt = dp[tight][has3][mod3][modp]
                        if cnt == 0:
                            continue
                        upper = curr_digit if tight else 9
                        for d in range(0, upper + 1):
                            new_tight = 1 if (tight and d == upper) else 0
                            new_has3 = 1 if (has3 or d == 3) else 0
                            new_mod3 = (mod3 + d) % 3
                            new_modp = (modp * 10 + d) % P
                            new_dp[new_tight][new_has3][new_mod3][new_modp] = (
                                new_dp[new_tight][new_has3][new_mod3][new_modp] + cnt
                            ) % MOD
        dp = new_dp
    total = 0
    for tight in [0, 1]:
        for has3 in [0, 1]:
            for mod3 in [0, 1, 2]:
                for modp in range(P):
                    if (has3 or mod3 == 0) and modp == 0:
                        total = (total + dp[tight][has3][mod3][modp]) % MOD
    return total

def main():
    import sys
    input = sys.stdin.read().split()
    A = input[0]
    B = input[1]
    P = int(input[2])
    
    A_minus_1 = subtract_one(A)
    
    aho_B = count_aho(B)
    aho_A_minus_1 = count_aho(A_minus_1)
    total_aho = (aho_B - aho_A_minus_1) % MOD
    
    aho_p_B = count_aho_p(B, P)
    aho_p_A_minus_1 = count_aho_p(A_minus_1, P)
    total_aho_p = (aho_p_B - aho_p_A_minus_1) % MOD
    
    answer = (total_aho - total_aho_p) % MOD
    print(answer)

if __name__ == "__main__":
    main()
0