結果

問題 No.260 世界のなんとか3
ユーザー terasa
提出日時 2022-11-04 22:08:10
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,634 bytes
コンパイル時間 152 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-07-18 19:57:00
合計ジャッジ時間 50,883 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 RE * 3 TLE * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

input = sys.stdin.readline


def readints(): return map(int, input().split())
def readlist(): return list(readints())
def readstr(): return input().rstrip()


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


def solve(N):
    dp = [[[0, 0] for _ in range(2)] for _ in range(24)]
    dp[0][0][0] = 1
    for i in range(len(N)):
        ndp = [[[0, 0] for _ in range(2)] for _ in range(24)]
        for j in range(24):
            for k in range(10):
                n = (j * 10 + k) % 24
                if k == 3:
                    ndp[n][1][1] += dp[j][1][1] + dp[j][0][1]
                else:
                    ndp[n][1][1] += dp[j][1][1]
                    ndp[n][0][1] += dp[j][0][1]

                if k < int(N[i]):
                    if k == 3:
                        ndp[n][1][1] += dp[j][1][0] + dp[j][0][0]
                    else:
                        ndp[n][1][1] += dp[j][1][0]
                        ndp[n][0][1] += dp[j][0][0]
                elif k == int(N[i]):
                    if k == 3:
                        ndp[n][1][0] += dp[j][1][0] + dp[j][0][0]
                    else:
                        ndp[n][1][0] += dp[j][1][0]
                        ndp[n][0][0] += dp[j][0][0]
                ndp[n][1][1] %= mod
                ndp[n][1][0] %= mod
                ndp[n][0][1] %= mod
                ndp[n][0][0] %= mod
        dp = ndp
    return dp


dpb = solve(B)
dpa = solve(str(int(A) - 1))

ans = 0
for i in range(24):
    for j in range(2):
        if (i % 3 == 0 or j == 1) and i % 8 != 0:
            ans += sum(dpb[i][j]) - sum(dpa[i][j])
            ans %= mod
print(ans)
0