結果

問題 No.658 テトラナッチ数列 Hard
コンテスト
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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])
0