結果
問題 | No.1269 I hate Fibonacci Number |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
import sysreadline = sys.stdin.readlinefrom collections import dequeclass AhoCorasick:def __init__(self, patterns):self.patterns = patternsself.children = [dict()]self.N = 1self.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.Nself._createfailure()def _add(self, i, p):vn = 0for pi in p:if pi in self.children[vn]:vn = self.children[vn][pi]else:self.children[vn][pi] = self.Nself.children.append(dict())self.match.append(False)vn = self.Nself.N += 1self.match[vn] = Truedef _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):#vnにsを付け足した時の遷移先while True:if s in self.children[vn]:return self.children[vn][s]if not vn:return vnvn = self.failure[vn]def idx(self, p):#文字列pのindexを返すvn = 0for pi in p:if pi in self.children[vn]:vn = self.children[vn][pi]else:return -1return vndef 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 resdef __repr__(self):SS = [None]*self.NSS[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+7Fib = []a, b = 1, 1while b <= R:Fib.append(b)a, b = b, a+bL -= 1a, b = 1, 1while b <= L:Fib.remove(b)a, b = b, a+bFib = [tuple(map(int, str(s))) for s in Fib]ahc = AhoCorasick(Fib)M = ahc.Ntable = ahc.getnxttable(10)dp = [0]*Mdp[0] = 1for _ in range(N):dp2 = [0]*Mfor i in range(M):if not dp[i]:continuefor s in range(10):vf = table[s*M + i]if not ahc.match[vf]:dp2[vf] = (dp2[vf] + dp[i])%MODdp = dp2[:]ans = MOD-1for d in dp:ans = (ans + d)%MODprint(ans)