結果

問題 No.260 世界のなんとか3
コンテスト
ユーザー norioc
提出日時 2025-05-19 00:27:19
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,550 bytes
コンパイル時間 483 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 59,512 KB
最終ジャッジ日時 2025-05-19 00:27:23
合計ジャッジ時間 4,252 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict


def f(s: str):
    ds = [int(c) for c in s]
    nd = len(ds)

    dp = defaultdict(int)
    dp[0, 0, 0, 0, 0] = 1

    for i in range(nd):
        for j in range(2):
            for b3 in range(2):  # 3 の桁があるか
                for m3 in range(3):  # mod 3
                    for m8 in range(8):  # mod 8
                        to = ds[i] if j == 0 else 9
                        for x in range(to+1):
                            nj = int(j | (x < to))
                            nb3 = int(b3 | (x == 3))
                            nm3 = (10*m3 + x) % 3
                            nm8 = (10*m8 + x) % 8
                            dp[i+1, nj, nb3, nm3, nm8] += dp[i, j, b3, m3, m8]
                            dp[i+1, nj, nb3, nm3, nm8] %= MOD

    res = 0
    for j in range(2):
        for b3 in range(2):
            for m3 in range(3):
                for m8 in range(1, 8):
                    if b3 or m3 == 0:
                        res += dp[nd, j, b3, m3, m8]
                        res %= MOD

    return res


def dec(s: str) -> str:
    if len(s) < 10:
        return str(int(s)-1)

    ds = [int(c) for c in s[::-1]]
    if ds[0] > 0:
        ds[0] -= 1
    else:
        ds[0] = 9
        for i in range(1, len(ds)):
            if ds[i] > 0:
                ds[i] -= 1
                break

            ds[i] = 9

    if ds[-1] == 0:
        ds.pop()

    return ''.join([str(c) for c in reversed(ds)])


MOD = 10**9 + 7
A, B = input().split()

ans = f(B) - f(dec(A))
print(ans)
0