結果

問題 No.260 世界のなんとか3
ユーザー lam6er
提出日時 2025-03-20 21:08:05
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,272 bytes
コンパイル時間 159 ms
コンパイル使用メモリ 82,580 KB
実行使用メモリ 236,184 KB
最終ジャッジ日時 2025-03-20 21:08:53
合計ジャッジ時間 4,345 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 MLE * 1
other AC * 1 TLE * 6 MLE * 20
権限があれば一括ダウンロードができます

ソースコード

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')
    return new_s if new_s else '0'
def count(s):
    n = len(s)
    memo = [defaultdict(int) for _ in range(n + 1)]
    memo[0][(True, 0, False, 0, True)] = 1
    
    for i in range(n):
        current_memo = memo[i]
        if not current_memo:
            continue
        next_memo = defaultdict(int)
        for state, cnt in current_memo.items():
            leading_zero_prev, sum_mod3_prev, has_3_prev, mod8_prev, tight_prev = state
            upper_digit = int(s[i]) if tight_prev else 9
            for d in range(0, upper_digit + 1):
                new_tight = tight_prev and (d == upper_digit)
                if leading_zero_prev:
                    if d == 0:
                        new_leading_zero = True
                        new_sum_mod3 = sum_mod3_prev
                        new_has_3 = has_3_prev
                        new_mod8 = mod8_prev
                    else:
                        new_leading_zero = False
                        new_sum_mod3 = d % 3
                        new_has_3 = (d == 3)
                        new_mod8 = d % 8
                else:
                    new_leading_zero = False
                    new_sum_mod3 = (sum_mod3_prev + d) % 3
                    new_has_3 = has_3_prev or (d == 3)
                    new_mod8 = (mod8_prev * 10 + d) % 8
                new_state = (new_leading_zero, new_sum_mod3, new_has_3, new_mod8, new_tight)
                next_memo[new_state] = (next_memo[new_state] + cnt) % MOD
        memo[i + 1] = next_memo
    
    total = 0
    for state, cnt in memo[n].items():
        leading_zero, sum_mod3, has_3, mod8, _ = state
        if leading_zero:
            continue
        if (sum_mod3 == 0 or has_3) and mod8 != 0:
            total = (total + cnt) % MOD
    return total
def main():
    A, B = sys.stdin.readline().split()
    a_minus_1 = subtract_one(A)
    ans = (count(B) - count(a_minus_1)) % MOD
    print(ans)
if __name__ == '__main__':
    main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0