結果

問題 No.315 世界のなんとか3.5
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:40:28
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,198 bytes
コンパイル時間 199 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 82,944 KB
最終ジャッジ日時 2025-06-12 14:40:35
合計ジャッジ時間 6,624 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12 TLE * 1 -- * 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
    carry = 1
    while i >= 0 and carry:
        digit = ord(s_list[i]) - ord('0')
        if digit >= carry:
            new_digit = digit - carry
            carry = 0
            s_list[i] = str(new_digit)
        else:
            new_digit = 10 + digit - carry
            carry = 1
            s_list[i] = str(new_digit)
        i -= 1
    # Remove leading zeros
    result = ''.join(s_list).lstrip('0')
    return result if result else '0'

def count_valid_numbers(X_digits, P):
    n = len(X_digits)
    leading_zero_true = defaultdict(int)
    leading_zero_true[True] = 1  # Initial state: tight=True, leading_zero=True
    leading_zero_false = defaultdict(int)

    for i in range(n):
        current_digit = X_digits[i]
        new_leading_zero_true = defaultdict(int)
        new_leading_zero_false = defaultdict(int)

        # Process leading_zero=True states
        for tight in leading_zero_true:
            cnt = leading_zero_true[tight]
            max_d = current_digit if tight else 9
            for d in range(0, max_d + 1):
                new_tight = tight and (d == max_d)
                if d == 0:
                    new_leading_zero_true[new_tight] = (new_leading_zero_true[new_tight] + cnt) % MOD
                else:
                    sum_mod3 = d % 3
                    has_three = (d == 3)
                    mod_p = d % 800
                    key = (new_tight, sum_mod3, has_three, mod_p)
                    new_leading_zero_false[key] = (new_leading_zero_false[key] + cnt) % MOD

        # Process leading_zero=False states
        for (tight, sum_mod3, has_three, mod_p), cnt in leading_zero_false.items():
            max_d = current_digit if tight else 9
            for d in range(0, max_d + 1):
                new_tight = tight and (d == max_d)
                new_sum_mod3 = (sum_mod3 + d) % 3
                new_has_three = has_three or (d == 3)
                new_mod_p = (mod_p * 10 + d) % 800
                key = (new_tight, new_sum_mod3, new_has_three, new_mod_p)
                new_leading_zero_false[key] = (new_leading_zero_false[key] + cnt) % MOD

        leading_zero_true.clear()
        leading_zero_true.update(new_leading_zero_true)
        leading_zero_false.clear()
        leading_zero_false.update(new_leading_zero_false)

    total = 0
    for (tight, sum_mod3, has_three, mod_p), cnt in leading_zero_false.items():
        if (sum_mod3 == 0 or has_three) and (mod_p % P != 0):
            total = (total + cnt) % MOD
    return total

def main():
    input_line = sys.stdin.read().split()
    A = input_line[0]
    B = input_line[1]
    P = int(input_line[2])

    A_minus_1 = subtract_one(A)
    A_minus_1_digits = [int(c) for c in A_minus_1] if A_minus_1 != '0' else []
    if not A_minus_1_digits:
        count_A = 0
    else:
        count_A = count_valid_numbers(A_minus_1_digits, P)

    B_digits = [int(c) for c in B]
    count_B = count_valid_numbers(B_digits, P)

    ans = (count_B - count_A) % MOD
    print(ans if ans >= 0 else ans + MOD)

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