結果

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

ソースコード

diff # 

import sys
from collections import defaultdict

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_non_aho(X_str):
    X = list(map(int, X_str))
    n = len(X)
    current = defaultdict(int)
    current[(1, 0, 0)] = 1  # (tight, mod3, has3)
    for pos in range(n):
        next_current = defaultdict(int)
        for (tight, mod3, has3), cnt in current.items():
            upper = X[pos] if tight else 9
            for d in range(0, upper + 1):
                new_tight = 1 if (tight and d == upper) else 0
                new_mod3 = (mod3 + d) % 3
                new_has3 = 1 if (has3 or d == 3) else 0
                if new_has3:
                    continue
                key = (new_tight, new_mod3, new_has3)
                next_current[key] = (next_current[key] + cnt) % MOD
        current = next_current
    res = 0
    for (tight, mod3, has3), cnt in current.items():
        if mod3 != 0 and has3 == 0:
            res = (res + cnt) % MOD
    return res

def count_eight(X_str):
    X = list(map(int, X_str))
    n = len(X)
    current = defaultdict(int)
    current[(1, 0)] = 1  # (tight, last3)
    for pos in range(n):
        next_current = defaultdict(int)
        for (tight, last3), cnt in current.items():
            upper = X[pos] if tight else 9
            for d in range(0, upper + 1):
                new_tight = 1 if (tight and d == upper) else 0
                new_last3 = (last3 * 10 + d) % 1000
                key = (new_tight, new_last3)
                next_current[key] = (next_current[key] + cnt) % MOD
        current = next_current
    res = 0
    for (tight, last3), cnt in current.items():
        if last3 % 8 == 0:
            res = (res + cnt) % MOD
    return res

def count_non_aho_eight(X_str):
    X = list(map(int, X_str))
    n = len(X)
    current = defaultdict(int)
    current[(1, 0, 0, 0)] = 1  # (tight, mod3, has3, last3)
    for pos in range(n):
        next_current = defaultdict(int)
        for (tight, mod3, has3, last3), cnt in current.items():
            upper = X[pos] if tight else 9
            for d in range(0, upper + 1):
                new_tight = 1 if (tight and d == upper) else 0
                new_mod3 = (mod3 + d) % 3
                new_has3 = 1 if (has3 or d == 3) else 0
                if new_has3:
                    continue
                new_last3 = (last3 * 10 + d) % 1000
                key = (new_tight, new_mod3, new_has3, new_last3)
                next_current[key] = (next_current[key] + cnt) % MOD
        current = next_current
    res = 0
    for (tight, mod3, has3, last3), cnt in current.items():
        if mod3 != 0 and has3 == 0 and last3 % 8 == 0:
            res = (res + cnt) % MOD
    return res

def main():
    A, B = sys.stdin.readline().split()
    A_minus_1 = subtract_one(A)
    
    # Compute total numbers: B - A + 1 mod MOD
    def str_mod(s, mod):
        res = 0
        for c in s:
            res = (res * 10 + int(c)) % mod
        return res
    total = (str_mod(B, MOD) - str_mod(A, MOD) + 1) % MOD
    if total < 0:
        total += MOD
    
    # Compute non_aho = count_non_aho(B) - count_non_aho(A-1)
    non_aho_B = count_non_aho(B)
    non_aho_A_minus_1 = count_non_aho(A_minus_1) if A != '0' else 0
    non_aho = (non_aho_B - non_aho_A_minus_1) % MOD
    
    # Compute eight = count_eight(B) - count_eight(A-1)
    eight_B = count_eight(B)
    eight_A_minus_1 = count_eight(A_minus_1) if A != '0' else 0
    eight = (eight_B - eight_A_minus_1) % MOD
    
    # Compute non_aho_eight = count_non_aho_eight(B) - count_non_aho_eight(A-1)
    non_aho_eight_B = count_non_aho_eight(B)
    non_aho_eight_A_minus_1 = count_non_aho_eight(A_minus_1) if A != '0' else 0
    non_aho_eight = (non_aho_eight_B - non_aho_eight_A_minus_1) % MOD
    
    # Answer = (total - non_aho) - (eight - non_aho_eight)
    answer = (total - non_aho - eight + non_aho_eight) % MOD
    print(answer if answer >= 0 else answer + MOD)

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