結果

問題 No.260 世界のなんとか3
ユーザー terasaterasa
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 55 ms
56,704 KB
testcase_01 MLE -
testcase_02 MLE -
testcase_03 MLE -
testcase_04 MLE -
testcase_05 MLE -
testcase_06 MLE -
testcase_07 MLE -
testcase_08 MLE -
testcase_09 MLE -
testcase_10 MLE -
testcase_11 MLE -
testcase_12 MLE -
testcase_13 MLE -
testcase_14 MLE -
testcase_15 MLE -
testcase_16 MLE -
testcase_17 MLE -
testcase_18 MLE -
testcase_19 MLE -
testcase_20 MLE -
testcase_21 MLE -
testcase_22 MLE -
testcase_23 MLE -
testcase_24 MLE -
testcase_25 MLE -
testcase_26 MLE -
testcase_27 AC 54 ms
55,808 KB
testcase_28 MLE -
testcase_29 MLE -
権限があれば一括ダウンロードができます

ソースコード

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