結果
問題 |
No.658 テトラナッチ数列 Hard
|
ユーザー |
![]() |
提出日時 | 2025-03-20 21:12:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 80 ms / 2,000 ms |
コード長 | 1,052 bytes |
コンパイル時間 | 358 ms |
コンパイル使用メモリ | 82,456 KB |
実行使用メモリ | 77,472 KB |
最終ジャッジ日時 | 2025-03-20 21:14:33 |
合計ジャッジ時間 | 1,604 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 8 |
ソースコード
Q = int(input()) queries = [int(input()) for _ in range(Q)] def find_period_table(): prev3, prev2, prev1, current = 0, 0, 0, 1 state_map = {} state_map[(prev3, prev2, prev1, current)] = 4 step = 4 while True: next_val = (prev3 + prev2 + prev1 + current) % 17 prev3, prev2, prev1, current = prev2, prev1, current, next_val step += 1 state = (prev3, prev2, prev1, current) if state in state_map: period = step - state_map[state] break state_map[state] = step # Generate the table for one period prev3, prev2, prev1, current = 0, 0, 0, 1 table = [] for _ in range(period): next_val = (prev3 + prev2 + prev1 + current) % 17 prev3, prev2, prev1, current = prev2, prev1, current, next_val table.append(current) return period, table period, table = find_period_table() for n in queries: if n <= 3: print(0) elif n == 4: print(1) else: idx = (n - 5) % period print(table[idx])