テトラナッチ数列 Hard [yukicoder No.658] - はまやんはまやんはまやん

前提知識

modをとった数列の周期性

解法

テトラナッチ数列について考察してみよう。
有名なフィボナッチ数列はmodを取ったものを考えると周期性があるという事実がある。
そのため、テトラナッチ数列にも周期性があるのではないかと考察できる。
実際これは正しい（鳩ノ巣原理）
そのため、周期を実験により求めよう。
すると、1周期4912でループしていることが分かる。
　
とても大きいnであっても4912でmodをとっても問題ない。
modを取るために0-indexedに変換してmodをとったら+1をして直す。
あとは、T[n]番目を答えるだけ。

int T[1010101];
//---------------------------------------------------------------------------------------------------
void _main() {
    T[1] = 0;
    T[2] = 0;
    T[3] = 0;
    T[4] = 1;

    rep(i, 5, 1010101) T[i] = (T[i - 1] + T[i - 2] + T[i - 3] + T[i - 4]) % 17;

    int Q; cin >> Q;
    rep(q, 0, Q) {
        ll n; cin >> n;
        n--;

        n %= 4912;

        n++;

        printf("%d\n", T[n]);
    }
}