結果

問題 No.1269 I hate Fibonacci Number
ユーザー tpyneriver
提出日時 2021-01-11 12:54:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 201 ms / 3,000 ms
コード長 3,417 bytes
コンパイル時間 310 ms
コンパイル使用メモリ 82,368 KB
実行使用メモリ 76,928 KB
最終ジャッジ日時 2024-11-21 09:01:12
合計ジャッジ時間 4,903 ms
ジャッジサーバーID
(参考情報)
judge1 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
readline = sys.stdin.readline
from collections import deque
class AhoCorasick:
def __init__(self, patterns):
self.patterns = patterns
self.children = [dict()]
self.N = 1
self.match = [False]
self.order = [0]
"""
self.match patterns
self.match True 使
"""
for i in range(len(patterns)):
self._add(i, patterns[i])
self.failure = [0]*self.N
self._createfailure()
def _add(self, i, p):
vn = 0
for pi in p:
if pi in self.children[vn]:
vn = self.children[vn][pi]
else:
self.children[vn][pi] = self.N
self.children.append(dict())
self.match.append(False)
vn = self.N
self.N += 1
self.match[vn] = True
def _createfailure(self):
Q = deque(self.children[0].values())
while Q:
vn = Q.pop()
self.order.append(vn)
fvn = self.failure[vn]
self.match[vn] |= self.match[fvn]
for fpi, vf in self.children[vn].items():
self.failure[vf] = self.nxt(fvn, fpi)
self.match[vf] |= self.match[vn]
Q.appendleft(vf)
def nxt(self, vn, s):
#vns
while True:
if s in self.children[vn]:
return self.children[vn][s]
if not vn:
return vn
vn = self.failure[vn]
def idx(self, p):
#pindex
vn = 0
for pi in p:
if pi in self.children[vn]:
vn = self.children[vn][pi]
else:
return -1
return vn
def getnxttable(self, sigma):
#[0, sigma)
#res[s*self.N + vn] = nxt(vn, s)
res = [0]*(self.N*sigma)
for l in self.order:
for s in range(sigma):
if s in self.children[l]:
res[s*self.N + l] = self.children[l][s]
else:
res[s*self.N + l] = res[s*self.N + self.failure[l]]
return res
def __repr__(self):
SS = [None]*self.N
SS[0] = ''
Q = deque([0])
while Q:
vn = Q.pop()
for c, vf in self.children[vn].items():
SS[vf] = f'{SS[vn]} {c}'
Q.appendleft(vf)
return '\n'.join(f'{i}:{SS[i]} {self.match[i]}' for i in range(self.N))
N, L, R = map(int, readline().split())
MOD = 10**9+7
Fib = []
a, b = 1, 1
while b <= R:
Fib.append(b)
a, b = b, a+b
L -= 1
a, b = 1, 1
while b <= L:
Fib.remove(b)
a, b = b, a+b
Fib = [tuple(map(int, str(s))) for s in Fib]
ahc = AhoCorasick(Fib)
M = ahc.N
table = ahc.getnxttable(10)
dp = [0]*M
dp[0] = 1
for _ in range(N):
dp2 = [0]*M
for i in range(M):
if not dp[i]:
continue
for s in range(10):
vf = table[s*M + i]
if not ahc.match[vf]:
dp2[vf] = (dp2[vf] + dp[i])%MOD
dp = dp2[:]
ans = MOD-1
for d in dp:
ans = (ans + d)%MOD
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0