結果

問題 No.260 世界のなんとか3
ユーザー norioc
提出日時 2025-05-19 00:01:01
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,128 bytes
コンパイル時間 716 ms
コンパイル使用メモリ 82,604 KB
実行使用メモリ 218,168 KB
最終ジャッジ日時 2025-05-19 00:01:06
合計ジャッジ時間 4,920 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample MLE * 3
other MLE * 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 = x < to
                            nb3 = int(b3 | (x == 3))
                            nm3 = (m3 + x) % 3
                            nm8 = (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()

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