問題一覧 > 通常問題

No.658 テトラナッチ数列 Hard

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

問題文

テトラナッチ数列というものがある。
テトラナッチ数列（ここでは{$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$

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

出力

$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
入力
7
99
9999
999999
99999999
9999999999
999999999999
99999999999999
出力
12
16
14
13
6
16
9

入力は32bit整数値におさまらないことがある。

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