結果

問題 No.315 世界のなんとか3.5
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:45:53
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,330 bytes
コンパイル時間 216 ms
コンパイル使用メモリ 82,316 KB
実行使用メモリ 93,304 KB
最終ジャッジ日時 2025-06-12 16:46:14
合計ジャッジ時間 5,139 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12 RE * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
MOD = 10**9 + 7

def subtract_one(s):
    s_list = list(s)
    i = len(s_list) - 1
    while i >= 0:
        if s_list[i] == '0':
            s_list[i] = '9'
            i -= 1
        else:
            s_list[i] = str(int(s_list[i]) - 1)
            break
    if i == -1:
        return '0' if len(s_list) == 0 or s_list[0] == '0' else ''.join(s_list)
    result = ''.join(s_list)
    if result.startswith('0') and len(result) > 1:
        return result.lstrip('0') or '0'
    return result

def count_ahou(X_str):
    from functools import lru_cache
    n = len(X_str)
    X = list(map(int, X_str))
    
    @lru_cache(maxsize=None)
    def dp(pos, mod3, has_3, tight):
        if pos == n:
            return 1 if (mod3 == 0 or has_3) else 0
        res = 0
        limit = X[pos] if tight else 9
        for d in range(0, limit + 1):
            new_tight = tight and (d == limit)
            new_mod3 = (mod3 * 10 + d) % 3
            new_has_3 = has_3 or (d == 3)
            res += dp(pos + 1, new_mod3, new_has_3, new_tight)
            res %= MOD
        return res % MOD
    total = dp(0, 0, False, True)
    dp.cache_clear()
    return total

def count_ahou_and_hajirai(X_str, P):
    from functools import lru_cache
    n = len(X_str)
    X = list(map(int, X_str))
    
    @lru_cache(maxsize=None)
    def dp(pos, mod3, has_3, modP, tight):
        if pos == n:
            return 1 if (mod3 == 0 or has_3) and modP == 0 else 0
        res = 0
        limit = X[pos] if tight else 9
        for d in range(0, limit + 1):
            new_tight = tight and (d == limit)
            new_mod3 = (mod3 * 10 + d) % 3
            new_has_3 = has_3 or (d == 3)
            new_modP = (modP * 10 + d) % P
            res += dp(pos + 1, new_mod3, new_has_3, new_modP, new_tight)
            res %= MOD
        return res % MOD
    total = dp(0, 0, False, 0, True)
    dp.cache_clear()
    return total

def main():
    A, B, P = sys.stdin.read().split()
    P = int(P)
    A_minus_1 = subtract_one(A)
    
    count_A = count_ahou(B) - count_ahou(A_minus_1)
    count_A %= MOD
    
    count_B = count_ahou_and_hajirai(B, P) - count_ahou_and_hajirai(A_minus_1, P)
    count_B %= MOD
    
    result = (count_A - count_B) % MOD
    print(result if result >= 0 else result + MOD)

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