結果

問題 No.260 世界のなんとか3
ユーザー qqqq
提出日時 2019-04-15 20:44:33
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 762 bytes
コンパイル時間 148 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 50,900 KB
最終ジャッジ日時 2024-09-22 08:02:14
合計ジャッジ時間 6,915 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff #

import numpy as np
from itertools import product
mod = 10**9+7

a, b = input().split()

def calc(s):
    keta = len(s)
    # keta, tight, mod3, is3, mod8
    dp = np.zeros((keta+1,2,3,2,8))
    dp[0][1][0][0][0] = 1
    for i, j, k, l, m in product(range(keta), range(2), range(3), range(2), range(8)):
        top = int(s[i]) if j else 9
        for n in range(top+1):
            dp[i+1][int(j and n== top)][(k+n)%3][int(l or n==3)][(2*m+n)%8] += dp[i][j][k][l][m]
            dp[i+1][int(j and n== top)][(k+n)%3][int(l or n==3)][(2*m+n)%8] %= mod
    ret = 0
    ret += dp[-1,0:2,0:3,1,1:].sum()
    ret += dp[-1,0:2,0,0:2,1:].sum()
    ret -= dp[-1,0:2,0,1,1:].sum()
    ret %= mod
    return int(ret)

ans = calc(b)-calc(str(int(a)-1))
ans %= mod
print(ans)
0