結果

問題 No.260 世界のなんとか3
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 15:12:27
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 4,430 bytes
コンパイル時間 182 ms
コンパイル使用メモリ 82,736 KB
実行使用メモリ 149,512 KB
最終ジャッジ日時 2025-06-12 15:12:39
合計ジャッジ時間 5,794 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 MLE * 2
other AC * 1 MLE * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

def count_mult3(n_str):
    MOD = 3
    n = len(n_str)
    from functools import lru_cache

    @lru_cache(maxsize=None)
    def dp(pos, mod, tight):
        if pos == n:
            return 1 if mod == 0 else 0
        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 = (mod * 10 + d) % MOD
            total += dp(pos + 1, new_mod, new_tight)
        return total

    return dp(0, 0, True)

def count_has3(n_str):
    n = len(n_str)
    from functools import lru_cache

    @lru_cache(maxsize=None)
    def dp(pos, has3, tight):
        if pos == n:
            return 1 if has3 else 0
        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_has = has3 or (d == 3)
            total += dp(pos + 1, new_has, new_tight)
        return total

    return dp(0, False, True)

def count_both_mult3_and_has3(n_str):
    MOD = 3
    n = len(n_str)
    from functools import lru_cache

    @lru_cache(maxsize=None)
    def dp(pos, mod, has3, tight):
        if pos == n:
            return 1 if (mod == 0 and has3) else 0
        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 = (mod * 10 + d) % MOD
            new_has = has3 or (d == 3)
            total += dp(pos + 1, new_mod, new_has, new_tight)
        return total

    return dp(0, 0, False, True)

def count_mult24(n_str):
    MOD = 24
    n = len(n_str)
    from functools import lru_cache

    @lru_cache(maxsize=None)
    def dp(pos, mod, tight):
        if pos == n:
            return 1 if mod == 0 else 0
        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 = (mod * 10 + d) % MOD
            total += dp(pos + 1, new_mod, new_tight)
        return total

    return dp(0, 0, True)

def count_mult8_and_has3(n_str):
    MOD = 8
    n = len(n_str)
    from functools import lru_cache

    @lru_cache(maxsize=None)
    def dp(pos, mod, has3, tight):
        if pos == n:
            return 1 if (mod == 0 and has3) else 0
        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 = (mod * 10 + d) % MOD
            new_has = has3 or (d == 3)
            total += dp(pos + 1, new_mod, new_has, new_tight)
        return total

    return dp(0, 0, False, True)

def count_mult24_and_has3(n_str):
    MOD = 24
    n = len(n_str)
    from functools import lru_cache

    @lru_cache(maxsize=None)
    def dp(pos, mod, has3, tight):
        if pos == n:
            return 1 if (mod == 0 and has3) else 0
        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 = (mod * 10 + d) % MOD
            new_has = has3 or (d == 3)
            total += dp(pos + 1, new_mod, new_has, new_tight)
        return total

    return dp(0, 0, False, True)

def compute_f(n_str):
    if n_str == '0':
        return 0
    a = count_mult3(n_str)
    b = count_has3(n_str)
    c = count_both_mult3_and_has3(n_str)
    return a + b - c

def compute_g(n_str):
    if n_str == '0':
        return 0
    a = count_mult24(n_str)
    b = count_mult8_and_has3(n_str)
    c = count_mult24_and_has3(n_str)
    return a + b - c

def main():
    import sys
    MOD = 10**9 + 7
    A, B = sys.stdin.read().split()
    
    A_minus_1 = subtract_one(A)
    
    f_A_minus_1 = compute_f(A_minus_1)
    f_B = compute_f(B)
    count_Ahoh = (f_B - f_A_minus_1) % MOD
    
    g_A_minus_1 = compute_g(A_minus_1)
    g_B = compute_g(B)
    count_Ahoh_and_Seishun = (g_B - g_A_minus_1) % MOD
    
    answer = (count_Ahoh - count_Ahoh_and_Seishun) % MOD
    print(answer)

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