結果

問題 No.260 世界のなんとか3
コンテスト
ユーザー norioc
提出日時 2025-05-19 00:17:51
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,166 bytes
コンパイル時間 646 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 59,204 KB
最終ジャッジ日時 2025-05-19 00:17:55
合計ジャッジ時間 4,499 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
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


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

# A = str(int(A)-1)

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