結果
| 問題 |
No.1269 I hate Fibonacci Number
|
| コンテスト | |
| ユーザー |
 lam6er
|
| 提出日時 | 2025-03-20 18:48:27 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,211 ms / 3,000 ms |
| コード長 | 6,332 bytes |
| コンパイル時間 | 223 ms |
| コンパイル使用メモリ | 82,132 KB |
| 実行使用メモリ | 77,460 KB |
| 最終ジャッジ日時 | 2025-03-20 18:49:58 |
| 合計ジャッジ時間 | 13,128 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 36 |
ソースコード
import sys
from collections import deque
MOD = 10**9 + 7
def main():
N, L, R = map(int, sys.stdin.readline().split())
# Generate Fibonacci numbers in [L, R]
fib = [1, 1]
while True:
next_fib = fib[-1] + fib[-2]
if next_fib > 1e18:
break
fib.append(next_fib)
S = []
for f in fib:
if L <= f <= R:
S.append(f)
# Deduplicate and sort
S = list(sorted(set(S)))
# Convert to strings and filter those with length <= N
str_S = []
max_len = 0
for s in S:
s_str = str(s)
if len(s_str) > N:
continue
str_S.append(s_str)
if len(s_str) > max_len:
max_len = len(s_str)
if not str_S:
# All possible numbers are valid
total = 0
for l in range(1, N+1):
if l == 1:
total = (total + 9) % MOD
else:
total = (total + 9 * pow(10, l-1, MOD)) % MOD
print(total % MOD)
return
# Build trie with failure links (Aho-Corasick automaton)
class Node:
__slots__ = ['transitions', 'fail', 'accepting', 'is_accepting']
def __init__(self):
self.transitions = {}
self.fail = 0
self.accepting = False # this node is an accepting state of a pattern
self.is_accepting = False # including failure links
nodes = [Node()]
root = 0
# Create root's transitions
# root's '0' transition is root itself (allows leading zeros)
nodes[root].transitions['0'] = root
for s in str_S:
current = root
for c in s:
if c in nodes[current].transitions:
current = nodes[current].transitions[c]
else:
new_node = Node()
new_node.transitions = {}
nodes.append(new_node)
nodes[current].transitions[c] = len(nodes)-1
current = len(nodes)-1
nodes[current].accepting = True
# Build failure links (BFS)
queue = deque()
nodes[root].fail = root
for c in nodes[root].transitions:
if c == '0' and nodes[root].transitions[c] == root:
continue
child_idx = nodes[root].transitions[c]
nodes[child_idx].fail = root
queue.append(child_idx)
while queue:
u_idx = queue.popleft()
u = nodes[u_idx]
for c, v_idx in u.transitions.items():
# Find fail for v_idx
f = u.fail
while True:
if c in nodes[f].transitions:
f_child = nodes[f].transitions[c]
break
else:
if f == root:
f_child = root
break
f = nodes[f].fail
nodes[v_idx].fail = f_child
queue.append(v_idx)
# Precompute is_accepting for all nodes
for u in nodes:
u.is_accepting = False
# Process nodes in BFS order to compute is_accepting (any ancestor is accepting)
for u_idx in range(len(nodes)):
current = u_idx
is_accepting = nodes[u_idx].accepting
current_fail = nodes[current].fail
while current_fail != root:
if nodes[current_fail].accepting:
is_accepting = True
break
current_fail = nodes[current_fail].fail
# Check if fail is root and has accepting
if current_fail == root:
if nodes[root].accepting:
is_accepting = True
nodes[u_idx].is_accepting = is_accepting or nodes[u_idx].accepting
# Now, the DP
# dp[i][j] is the number of strings of length i ending at state j without having triggered any accepting state
dp_prev = [0] * len(nodes)
dp_prev[root] = 1 # empty string
total = 0
for i in range(1, N+1):
dp_curr = [0] * len(nodes)
# Digits allowed for this position:
# first character: 1-9
# others: 0-9
for j in range(len(nodes)):
if dp_prev[j] == 0:
continue
if i == 1:
# first character: 1-9
for c in map(str, range(1, 10)):
current_state = j
# Follow transitions, but with failure links
next_state = current_state
while True:
if c in nodes[next_state].transitions:
next_state = nodes[next_state].transitions[c]
break
else:
if next_state == root:
next_state = root
break
next_state = nodes[next_state].fail
# Now next_state is resolved
if nodes[next_state].is_accepting:
continue
# Add to dp_curr
dp_curr[next_state] = (dp_curr[next_state] + dp_prev[j]) % MOD
else:
# other characters: 0-9
for c in map(str, range(0, 10)):
current_state = j
# Follow transitions with failure links
next_state = current_state
while True:
if c in nodes[next_state].transitions:
next_state = nodes[next_state].transitions[c]
break
else:
if next_state == root:
next_state = root
break
next_state = nodes[next_state].fail
if nodes[next_state].is_accepting:
continue
dp_curr[next_state] = (dp_curr[next_state] + dp_prev[j]) % MOD
# Update total
for state in range(len(dp_curr)):
if state == root and i == 0:
continue
if dp_curr[state] == 0:
continue
total = (total + dp_curr[state]) % MOD
dp_prev = dp_curr
print(total % MOD)
if __name__ == "__main__":
main()