結果

問題 No.657 テトラナッチ数列 Easy
コンテスト
ユーザー lam6er
提出日時 2025-03-20 18:58:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 102 ms / 2,000 ms
コード長 1,053 bytes
コンパイル時間 204 ms
コンパイル使用メモリ 82,728 KB
実行使用メモリ 77,000 KB
最終ジャッジ日時 2025-03-20 18:59:16
合計ジャッジ時間 2,288 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

def precompute():
    mod = 17
    sequence = [0, 0, 0, 1]  # T1 to T4
    state_map = {}
    current_state = (0, 0, 0, 1)
    state_map[current_state] = 4  # next index to be added is 4 (T5)
    
    cycle_length = None
    cycle_start = None
    n = 4  # current index is 3 (T4), next to compute is T5 (index 4)
    
    while True:
        next_val = sum(current_state) % mod
        sequence.append(next_val)
        n += 1  # now n is the next index + 1 after appending
        new_state = (current_state[1], current_state[2], current_state[3], next_val)
        if new_state in state_map:
            cycle_start = state_map[new_state]
            cycle_length = n - cycle_start
            break
        else:
            state_map[new_state] = n
        current_state = new_state
    
    return sequence, cycle_length

sequence, cycle_length = precompute()

Q = int(input())
for _ in range(Q):
    n = int(input())
    if n <= 4:
        print(sequence[n-1])
    else:
        offset = (n - 5) % cycle_length
        print(sequence[4 + offset])
0