問題一覧 > 通常問題

No.657 テトラナッチ数列 Easy

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 290
作問者 : ミドリムシミドリムシ / テスター : cielciel
2 ProblemId : 1971 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-03-02 01:18:54

問題文

テトラナッチ数列というものがある。
テトラナッチ数列(ここでは{$T_n$})は次のように定義される。
・$T_1 = 0,$ $T_2 = 0,$ $T_3 = 0,$ $T_4 = 1$
・$T_k = T_{k-1}$ $+$ $T_{k-2}$ $+$ $T_{k-3}$ $+$ $T_{k-4}$

テトラナッチ数列の$n_i$番目の項$T_{n_i}$を17で割った余りを求めなさい。

入力

$Q$
$n_1$
$n_2$

:

$n_Q$

入力は$Q+1$行与えられ、
1行目にはクエリの回数を表す整数$Q(1 \leq Q \leq 10^4)$、
$i+1(1 \leq i \leq Q)$行目には整数$n_i(1 \leq n_i \leq 10^6)$
が与えられる。

出力

$Q$行出力し、
$i(1 \leq i \leq Q)$行目にはテトラナッチ数列の$n_i$番目の項$T_{n_i}$を17で割った余りを出力せよ。
末尾に改行を入れること。

サンプル

サンプル1
入力
2
3
10
出力
0
12

テトラナッチ数列の3番目の項は0、10番目の項は29なので、17で割った余りは12。

サンプル2
入力
6
3
2
1
3
1
4
出力
0
0
0
0
0
1

入力は全て違う値とは限らない。

サンプル3
入力
6
9
99
999
9999
99999
999999
出力
15
12
2
16
4
14

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。