結果

問題 No.315 世界のなんとか3.5
ユーザー lam6er
提出日時 2025-04-16 16:29:26
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,659 bytes
コンパイル時間 286 ms
コンパイル使用メモリ 82,260 KB
実行使用メモリ 77,888 KB
最終ジャッジ日時 2025-04-16 16:31:04
合計ジャッジ時間 9,289 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 < 0:
        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_aho(S):
    n = len(S)
    current_dp = [[[0]*3 for _ in range(2)] for __ in range(2)]
    current_dp[1][0][0] = 1
    for i in range(n):
        next_dp = [[[0]*3 for _ in range(2)] for __ in range(2)]
        for tight in [0, 1]:
            for has_three in [0, 1]:
                for mod3 in [0, 1, 2]:
                    cnt = current_dp[tight][has_three][mod3]
                    if cnt == 0:
                        continue
                    max_d = int(S[i]) if tight else 9
                    for d in range(0, max_d + 1):
                        new_tight = 1 if (tight and d == max_d) else 0
                        new_has_three = 1 if (has_three or d == 3) else 0
                        new_mod3 = (mod3 + d) % 3
                        next_dp[new_tight][new_has_three][new_mod3] = (
                            next_dp[new_tight][new_has_three][new_mod3] + cnt
                        ) % MOD
        current_dp = next_dp
    res = 0
    for tight in [0, 1]:
        for has_three in [0, 1]:
            for mod3 in [0, 1, 2]:
                if has_three or mod3 == 0:
                    res = (res + current_dp[tight][has_three][mod3]) % MOD
    return res

def count_aho_and_p(S, P):
    n = len(S)
    current_dp = [[[[0]*P for _ in range(3)] for __ in range(2)] for ___ in range(2)]
    current_dp[1][0][0][0] = 1
    for i in range(n):
        next_dp = [[[[0]*P for _ in range(3)] for __ in range(2)] for ___ in range(2)]
        for tight in [0, 1]:
            for has_three in [0, 1]:
                for mod3 in [0, 1, 2]:
                    for modP in range(P):
                        cnt = current_dp[tight][has_three][mod3][modP]
                        if cnt == 0:
                            continue
                        max_d = int(S[i]) if tight else 9
                        for d in range(0, max_d + 1):
                            new_tight = 1 if (tight and d == max_d) else 0
                            new_has_three = 1 if (has_three or d == 3) else 0
                            new_mod3 = (mod3 + d) % 3
                            new_modP = (modP * 10 + d) % P
                            next_dp[new_tight][new_has_three][new_mod3][new_modP] = (
                                next_dp[new_tight][new_has_three][new_mod3][new_modP] + cnt
                            ) % MOD
        current_dp = next_dp
    res = 0
    for tight in [0, 1]:
        for has_three in [0, 1]:
            for mod3 in [0, 1, 2]:
                for modP in range(P):
                    if (has_three or mod3 == 0) and modP == 0:
                        res = (res + current_dp[tight][has_three][mod3][modP]) % MOD
    return res

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)
    
    count_B_aho = count_aho(B)
    count_B_aho_and_p = count_aho_and_p(B, P)
    f_B = (count_B_aho - count_B_aho_and_p) % MOD
    
    if A_minus_1 == '0':
        f_Aminus1 = 0
    else:
        count_Aminus1_aho = count_aho(A_minus_1)
        count_Aminus1_aho_and_p = count_aho_and_p(A_minus_1, P)
        f_Aminus1 = (count_Aminus1_aho - count_Aminus1_aho_and_p) % MOD
    
    answer = (f_B - f_Aminus1) % MOD
    print(answer)

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