結果

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

ソースコード

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:
        s_list[i] = str(int(s_list[i]) - 1)
    new_s = ''.join(s_list).lstrip('0')
    if not new_s:
        return '0'
    return new_s

def count_valid_numbers(X_str):
    if X_str == '0':
        return 0
    n = len(X_str)
    dp = defaultdict(int)
    dp[(0, 0, False, True, True)] = 1

    for i in range(n):
        next_dp = defaultdict(int)
        current_digit = int(X_str[i])
        for state, cnt in dp.items():
            sum_mod3, mod8, has_three, tight, leading_zero = state
            max_d = current_digit 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 new_leading_zero:
                    new_sum_mod3 = 0
                    new_mod8 = 0
                else:
                    if leading_zero:
                        new_sum_mod3 = d % 3
                        new_mod8 = d % 8
                    else:
                        new_sum_mod3 = (sum_mod3 + d) % 3
                        new_mod8 = (mod8 * 10 + d) % 8
                new_has_three = has_three or (d == 3)
                new_state = (new_sum_mod3, new_mod8, new_has_three, new_tight, new_leading_zero)
                next_dp[new_state] = (next_dp[new_state] + cnt) % MOD
        dp = next_dp

    total = 0
    for state, cnt in dp.items():
        sum_mod3, mod8, has_three, _, leading_zero = state
        if leading_zero:
            continue
        condition1 = (sum_mod3 == 0) or has_three
        condition2 = (mod8 != 0)
        if condition1 and condition2:
            total = (total + cnt) % MOD
    return total

def main():
    A, B = sys.stdin.readline().split()
    A_minus_1 = subtract_one(A)
    count_B = count_valid_numbers(B)
    count_A_minus_1 = count_valid_numbers(A_minus_1)
    result = (count_B - count_A_minus_1) % MOD
    print(result)

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