結果

問題 No.260 世界のなんとか3
コンテスト
ユーザー lam6er
提出日時 2025-04-15 21:18:40
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,159 bytes
コンパイル時間 413 ms
コンパイル使用メモリ 82,384 KB
実行使用メモリ 88,280 KB
最終ジャッジ日時 2025-04-15 21:25:02
合計ジャッジ時間 36,631 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 MLE * 2
other AC * 1 TLE * 3 MLE * 23
権限があれば一括ダウンロードができます

ソースコード

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)
    j = 0
    while j < len(s_list) and s_list[j] == '0':
        j += 1
    if j >= len(s_list):
        return '0'
    res = ''.join(s_list[j:])
    return res if res else '0'

def compute(X):
    if X == '0':
        return 0
    digits = list(map(int, X))
    n = len(digits)
    from collections import defaultdict
    current_dp = defaultdict(int)
    current_dp[(True, True, 0, False, 0)] = 1  # (tight, leading_zero, mod3, has3, mod8)
    
    for pos in range(n):
        next_dp = defaultdict(int)
        for state, cnt in current_dp.items():
            tight, leading_zero, mod3, has3, mod8 = state
            max_d = digits[pos] if tight else 9
            for d in range(0, max_d + 1):
                new_tight = tight and (d == max_d)
                new_leading_zero = leading_zero and (d == 0)
                
                if leading_zero:
                    if d == 0:
                        new_mod3_ = 0
                        new_has3_ = False
                        new_mod8_ = 0
                    else:
                        new_mod3_ = d % 3
                        new_has3_ = (d == 3)
                        new_mod8_ = d % 8
                else:
                    new_mod3_ = (mod3 + d) % 3
                    new_has3_ = has3 or (d == 3)
                    new_mod8_ = (mod8 * 10 + d) % 8
                
                new_state = (new_tight, new_leading_zero, new_mod3_, new_has3_, new_mod8_)
                next_dp[new_state] = (next_dp[new_state] + cnt) % MOD
        current_dp = next_dp
    
    total = 0
    for state, cnt in current_dp.items():
        tight, leading_zero, mod3, has3, mod8 = state
        if leading_zero:
            continue
        if (mod3 == 0 or has3) and mod8 != 0:
            total = (total + cnt) % MOD
    return total

A, B = input().split()
A_minus_1 = subtract_one(A)
result = (compute(B) - compute(A_minus_1)) % MOD
print(result)
0