結果

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

ソースコード

diff # 

MOD = 10**9 + 7

def generate_min(k):
    return '1' + '0' * (k - 1)

def generate_max(k):
    return '9' * k

def count_range(lower_str, upper_str, k):
    from collections import defaultdict

    current = defaultdict(int)
    first_min = int(lower_str[0])
    first_max = int(upper_str[0])
    for d in range(first_min, first_max + 1):
        new_tight_lower = (d == first_min)
        new_tight_upper = (d == first_max)
        new_has_three = (d == 3)
        new_mod3 = d % 3
        new_mod8 = d % 8
        current[(new_tight_lower, new_tight_upper, new_has_three, new_mod3, new_mod8)] += 1

    for pos in range(1, k):
        next_dp = defaultdict(int)
        for (tight_lower, tight_upper, has_three, mod3, mod8), cnt in current.items():
            min_d = int(lower_str[pos]) if tight_lower else 0
            max_d = int(upper_str[pos]) if tight_upper else 9
            for d in range(min_d, max_d + 1):
                new_tl = tight_lower and (d == int(lower_str[pos]))
                new_tu = tight_upper and (d == int(upper_str[pos]))
                new_ht = has_three or (d == 3)
                new_m3 = (mod3 * 10 + d) % 3
                new_m8 = (mod8 * 10 + d) % 8
                key = (new_tl, new_tu, new_ht, new_m3, new_m8)
                next_dp[key] = (next_dp[key] + cnt) % MOD
        current = next_dp

    total = 0
    for (tl, tu, has_three, mod3, mod8), cnt in current.items():
        if (mod3 == 0 or has_three) and mod8 != 0:
            total = (total + cnt) % MOD
    return total

def main():
    A, B = input().split()
    len_A = len(A)
    len_B = len(B)
    total = 0

    if len_A < len_B:
        # Process intermediate lengths
        for k in range(len_A + 1, len_B):
            min_str = generate_min(k)
            max_str = generate_max(k)
            res = count_range(min_str, max_str, k)
            total = (total + res) % MOD

        # Process len_A digits
        upper_len_A = generate_max(len_A)
        res = count_range(A, upper_len_A, len_A)
        total = (total + res) % MOD

        # Process len_B digits
        lower_len_B = generate_min(len_B)
        res = count_range(lower_len_B, B, len_B)
        total = (total + res) % MOD
    else:
        # Same length
        res = count_range(A, B, len_A)
        total = (total + res) % MOD

    print(total % MOD)

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