結果

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

ソースコード

diff # 

import sys
from collections import defaultdict

MOD = 10**9 + 7

def decrement_string(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)
    result = ''.join(s_list).lstrip('0')
    return result if result else '0'

def compute(s):
    digits = list(map(int, s))
    n = len(digits)
    dp = [defaultdict(int) for _ in range(n + 1)]
    dp[0][(True, True, False, 0, 0)] = 1
    for pos in range(n):
        current_dp = dp[pos]
        next_dp = defaultdict(int)
        for state, count in current_dp.items():
            tight, leading_zero, has_three, sum_mod3, num_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)
                new_has_three = has_three or (d == 3)
                if leading_zero:
                    if d == 0:
                        new_sum_mod3 = sum_mod3
                    else:
                        new_sum_mod3 = d % 3
                else:
                    new_sum_mod3 = (sum_mod3 + d) % 3
                if new_leading_zero:
                    new_num_mod8 = 0
                else:
                    if leading_zero:
                        new_num_mod8 = d % 8
                    else:
                        new_num_mod8 = (num_mod8 * 10 + d) % 8
                new_state = (new_tight, new_leading_zero, new_has_three, new_sum_mod3, new_num_mod8)
                next_dp[new_state] = (next_dp[new_state] + count) % MOD
        dp[pos + 1] = next_dp
    total = 0
    for state, count in dp[n].items():
        tight, leading_zero, has_three, sum_mod3, num_mod8 = state
        if leading_zero:
            continue
        if (has_three or (sum_mod3 == 0)) and (num_mod8 != 0):
            total = (total + count) % MOD
    return total

def main():
    A, B = sys.stdin.readline().split()
    a_minus_1 = decrement_string(A)
    ans = (compute(B) - compute(a_minus_1)) % MOD
    print(ans)

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