結果

問題 No.315 世界のなんとか3.5
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:44:59
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 5,731 bytes
コンパイル時間 302 ms
コンパイル使用メモリ 82,912 KB
実行使用メモリ 77,524 KB
最終ジャッジ日時 2025-06-12 16:45:05
合計ジャッジ時間 4,177 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12 RE * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
MOD = 10**9 + 7

def main():
    A, B, P = sys.stdin.read().split()
    P = int(P)
    LCM_val = LCM(3, P)

    # Compute Ahoh_count
    count_3 = compute_count_divisible(3, A, B)
    count_has3 = (compute_count_range(A, B) - compute_count_no3(A, B)) % MOD
    count_3_and_has3 = compute_count_3_and_has3(A, B)
    Ahoh_count = (count_3 + count_has3 - count_3_and_has3) % MOD

    # Compute count_3_and_div_P
    count_3_and_div_P = compute_count_divisible(LCM_val, A, B)

    # Compute count_has3_and_div_P
    count_div_P = compute_count_divisible(P, A, B)
    count_div_P_without_3 = compute_count_divisible_P_without_3(P, A, B)
    count_has3_and_div_P = (count_div_P - count_div_P_without_3) % MOD

    # Compute count_3_and_has3_and_div_P
    count_div_LCM = compute_count_divisible(LCM_val, A, B)
    count_div_LCM_without_3 = compute_count_divisible_LCM_without_3(LCM_val, A, B)
    count_3_and_has3_and_div_P = (count_div_LCM - count_div_LCM_without_3) % MOD

    # Compute hajiwarai_count_Ahoh
    hajiwarai_count_Ahoh = (count_3_and_div_P + count_has3_and_div_P - count_3_and_has3_and_div_P) % MOD

    answer = (Ahoh_count - hajiwarai_count_Ahoh) % MOD
    print(answer)

def LCM(a, b):
    from math import gcd
    return a * b // gcd(a, b)

def compute_count_range(a, b):
    a_mod = mod_num(a, MOD)
    b_mod = mod_num(b, MOD)
    return (b_mod - a_mod + 1 + MOD) % MOD

def mod_num(n_str, mod):
    res = 0
    for c in n_str:
        res = (res * 10 + int(c)) % mod
    return res

def compute_count_divisible(d, a, b):
    def count_up_to(n_str):
        if len(n_str) == 0:
            return 0
        n = int(n_str)
        return (n // d) % MOD
    count_b = count_up_to(b)
    a_minus_1 = str(int(a)-1) if a != '0' else '0'
    count_a_minus_1 = count_up_to(a_minus_1)
    return (count_b - count_a_minus_1 + MOD) % MOD

def compute_count_no3(a, b):
    def count_up_to(n_str):
        memo = {}
        def dp(pos, tight, has3):
            if pos == len(n_str):
                return 0 if has3 else 1
            key = (pos, tight, has3)
            if key in memo:
                return memo[key]
            limit = int(n_str[pos]) if tight else 9
            total = 0
            for d in range(0, limit + 1):
                new_tight = tight and (d == limit)
                new_has3 = has3 or (d == 3)
                if new_has3:
                    continue
                total += dp(pos + 1, new_tight, new_has3)
            memo[key] = total % MOD
            return memo[key]
        return dp(0, True, False)
    count_b = count_up_to(b)
    a_minus_1 = str(int(a) - 1) if a != '0' else '0'
    count_a_minus_1 = count_up_to(a_minus_1)
    return (count_b - count_a_minus_1 + MOD) % MOD

def compute_count_3_and_has3(a, b):
    def count_up_to(n_str):
        memo = {}
        def dp(pos, tight, mod3, has3):
            if pos == len(n_str):
                return 1 if (mod3 == 0 and has3) else 0
            key = (pos, tight, mod3, has3)
            if key in memo:
                return memo[key]
            limit = int(n_str[pos]) if tight else 9
            total = 0
            for d in range(0, limit + 1):
                new_tight = tight and (d == limit)
                new_mod3 = (mod3 * 10 + d) % 3
                new_has3 = has3 or (d == 3)
                total += dp(pos + 1, new_tight, new_mod3, new_has3)
            memo[key] = total % MOD
            return memo[key]
        return dp(0, True, 0, False)
    count_b = count_up_to(b)
    a_minus_1 = str(int(a) - 1) if a != '0' else '0'
    count_a_minus_1 = count_up_to(a_minus_1)
    return (count_b - count_a_minus_1 + MOD) % MOD

def compute_count_divisible_P_without_3(P, a, b):
    def count_up_to(n_str):
        memo = {}
        def dp(pos, tight, modP, has3):
            if pos == len(n_str):
                return 1 if (modP == 0 and not has3) else 0
            key = (pos, tight, modP, has3)
            if key in memo:
                return memo[key]
            limit = int(n_str[pos]) if tight else 9
            total = 0
            for d in range(0, limit + 1):
                new_tight = tight and (d == limit)
                new_modP = (modP * 10 + d) % P
                new_has3 = has3 or (d == 3)
                if new_has3:
                    continue
                total += dp(pos + 1, new_tight, new_modP, new_has3)
            memo[key] = total % MOD
            return memo[key]
        return dp(0, True, 0, False)
    count_b = count_up_to(b)
    a_minus_1 = str(int(a) - 1) if a != '0' else '0'
    count_a_minus_1 = count_up_to(a_minus_1)
    return (count_b - count_a_minus_1 + MOD) % MOD

def compute_count_divisible_LCM_without_3(LCM_val, a, b):
    def count_up_to(n_str):
        memo = {}
        def dp(pos, tight, mod_LCM, has3):
            if pos == len(n_str):
                return 1 if (mod_LCM == 0 and not has3) else 0
            key = (pos, tight, mod_LCM, has3)
            if key in memo:
                return memo[key]
            limit = int(n_str[pos]) if tight else 9
            total = 0
            for d in range(0, limit + 1):
                new_tight = tight and (d == limit)
                new_mod_LCM = (mod_LCM * 10 + d) % LCM_val
                new_has3 = has3 or (d == 3)
                if new_has3:
                    continue
                total += dp(pos + 1, new_tight, new_mod_LCM, new_has3)
            memo[key] = total % MOD
            return memo[key]
        return dp(0, True, 0, False)
    count_b = count_up_to(b)
    a_minus_1 = str(int(a) - 1) if a != '0' else '0'
    count_a_minus_1 = count_up_to(a_minus_1)
    return (count_b - count_a_minus_1 + MOD) % MOD

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