結果

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

ソースコード

diff # 

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_3(s):
    MOD = 3
    from functools import lru_cache
    n = len(s)
    @lru_cache(maxsize=None)
    def dp(pos, tight, mod):
        if pos == n:
            return 1 if mod == 0 else 0
        limit = int(s[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_tight, new_mod)
        return total
    return dp(0, True, 0)

def count_has3(s):
    from functools import lru_cache
    n = len(s)
    @lru_cache(maxsize=None)
    def dp(pos, tight, has3):
        if pos == n:
            return 1 if has3 else 0
        limit = int(s[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)
            total += dp(pos + 1, new_tight, new_has3)
        return total
    return dp(0, True, False)

def count_both_3_has3(s):
    MOD = 3
    from functools import lru_cache
    n = len(s)
    @lru_cache(maxsize=None)
    def dp(pos, tight, mod, has3):
        if pos == n:
            return 1 if (mod == 0 and has3) else 0
        limit = int(s[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_has3 = has3 or (d == 3)
            total += dp(pos + 1, new_tight, new_mod, new_has3)
        return total
    return dp(0, True, 0, False)

def count_8(s):
    MOD = 8
    from functools import lru_cache
    n = len(s)
    @lru_cache(maxsize=None)
    def dp(pos, tight, mod):
        if pos == n:
            return 1 if mod == 0 else 0
        limit = int(s[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_tight, new_mod)
        return total
    return dp(0, True, 0)

def count_24(s):
    MOD = 24
    from functools import lru_cache
    n = len(s)
    @lru_cache(maxsize=None)
    def dp(pos, tight, mod):
        if pos == n:
            return 1 if mod == 0 else 0
        limit = int(s[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_tight, new_mod)
        return total
    return dp(0, True, 0)

def count_8_has3(s):
    MOD = 8
    from functools import lru_cache
    n = len(s)
    @lru_cache(maxsize=None)
    def dp(pos, tight, mod, has3):
        if pos == n:
            return 1 if (mod == 0 and has3) else 0
        limit = int(s[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_has3 = has3 or (d == 3)
            total += dp(pos + 1, new_tight, new_mod, new_has3)
        return total
    return dp(0, True, 0, False)

def count_24_has3(s):
    MOD = 24
    from functools import lru_cache
    n = len(s)
    @lru_cache(maxsize=None)
    def dp(pos, tight, mod, has3):
        if pos == n:
            return 1 if (mod == 0 and has3) else 0
        limit = int(s[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_has3 = has3 or (d == 3)
            total += dp(pos + 1, new_tight, new_mod, new_has3)
        return total
    return dp(0, True, 0, False)

MOD = 10**9 + 7

A, B = input().split()

def compute(s):
    return s

A_str = A
B_str = B

# Calculate C = count_3 + count_has3 - count_both
c3_B = count_3(B_str)
c3_A_minus1 = count_3(subtract_one(A_str)) if A != '0' else 0
count_3_total = (c3_B - c3_A_minus1) % MOD

c_has3_B = count_has3(B_str)
c_has3_A_minus1 = count_has3(subtract_one(A_str)) if A != '0' else 0
count_has3_total = (c_has3_B - c_has3_A_minus1) % MOD

c_both_B = count_both_3_has3(B_str)
c_both_A_minus1 = count_both_3_has3(subtract_one(A_str)) if A != '0' else 0
count_both_total = (c_both_B - c_both_A_minus1) % MOD

C = (count_3_total + count_has3_total - count_both_total) % MOD

# Calculate D = count_24 + count_8_has3 - count_24_has3
c24_B = count_24(B_str)
c24_A_minus1 = count_24(subtract_one(A_str)) if A != '0' else 0
count_24_total = (c24_B - c24_A_minus1) % MOD

c8_has3_B = count_8_has3(B_str)
c8_has3_A_minus1 = count_8_has3(subtract_one(A_str)) if A != '0' else 0
count_8_has3_total = (c8_has3_B - c8_has3_A_minus1) % MOD

c24_has3_B = count_24_has3(B_str)
c24_has3_A_minus1 = count_24_has3(subtract_one(A_str)) if A != '0' else 0
count_24_has3_total = (c24_has3_B - c24_has3_A_minus1) % MOD

D = (count_24_total + count_8_has3_total - count_24_has3_total) % MOD

result = (C - D) % MOD
print(result if result >= 0 else result + MOD)
0