結果
問題 |
No.1269 I hate Fibonacci Number
|
ユーザー |
![]() |
提出日時 | 2025-04-09 20:58:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 695 ms / 3,000 ms |
コード長 | 3,227 bytes |
コンパイル時間 | 577 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 77,808 KB |
最終ジャッジ日時 | 2025-04-09 21:00:10 |
合計ジャッジ時間 | 9,270 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
import sys from collections import deque MOD = 10**9 + 7 def generate_fib(L, R): fibs = set() a, b = 1, 1 while a <= R: if a >= L: fibs.add(str(a)) a, b = b, a + b return fibs def build_automaton(patterns): nodes = [{'children': {}, 'fail': 0, 'danger': False}] root = 0 for pattern in patterns: current = root for c in pattern: if c not in nodes[current]['children']: new_node = len(nodes) nodes.append({'children': {}, 'fail': 0, 'danger': False}) nodes[current]['children'][c] = new_node current = nodes[current]['children'][c] nodes[current]['danger'] = True queue = deque() for c in nodes[root]['children']: child = nodes[root]['children'][c] nodes[child]['fail'] = root queue.append(child) while queue: u_idx = queue.popleft() u = nodes[u_idx] for c, child_idx in u['children'].items(): fail = u['fail'] while fail != root and c not in nodes[fail]['children']: fail = nodes[fail]['fail'] child_fail = nodes[fail]['children'].get(c, root) nodes[child_idx]['fail'] = child_fail if nodes[child_fail]['danger']: nodes[child_idx]['danger'] = True queue.append(child_idx) trans_table = [{} for _ in range(len(nodes))] for u_idx in range(len(nodes)): for c in '0123456789': v_idx = u_idx while True: if c in nodes[v_idx]['children']: trans_table[u_idx][c] = nodes[v_idx]['children'][c] break else: if v_idx == root: trans_table[u_idx][c] = root break v_idx = nodes[v_idx]['fail'] danger = [False] * len(nodes) for u_idx in range(len(nodes)): current = u_idx while True: if nodes[current]['danger']: danger[u_idx] = True break if current == root: break current = nodes[current]['fail'] return trans_table, danger def main(): N, L, R = map(int, sys.stdin.readline().split()) fibs = generate_fib(L, R) if not fibs: allowed_chars = 9 * (10**(N) - 1) // 9 print(allowed_chars % MOD) return trans_table, danger = build_automaton(fibs) len_nodes = len(trans_table) dp_prev = [0] * len_nodes dp_prev[0] = 1 total = 0 for step in range(N): dp_next = [0] * len_nodes for u in range(len_nodes): if dp_prev[u] == 0: continue if step == 0: chars = [str(d) for d in range(1, 10)] else: chars = [str(d) for d in range(10)] for c in chars: v = trans_table[u][c] if danger[v]: continue dp_next[v] = (dp_next[v] + dp_prev[u]) % MOD dp_prev = dp_next total = (total + sum(dp_prev)) % MOD print(total % MOD) if __name__ == "__main__": main()