結果

問題 No.260 世界のなんとか3
コンテスト
ユーザー terasa
提出日時 2022-11-04 22:06:30
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,851 bytes
コンパイル時間 184 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 79,232 KB
最終ジャッジ日時 2024-07-18 19:54:17
合計ジャッジ時間 9,550 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 MLE * 2
other AC * 1 MLE * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import itertools
import heapq
import bisect
from collections import deque, defaultdict
from functools import lru_cache, cmp_to_key

input = sys.stdin.readline

# for AtCoder Easy test
if __file__ != 'prog.py':
    sys.setrecursionlimit(10 ** 6)


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