フィボナッチフィボナッチ数 [yukicoder No.534] - はまやんはまやんはまやん

https://yukicoder.me/problems/no/534

このページにこんな一節がある。
「ｐ＝±２（ｍｏｄ５）のとき，ｆ（ｐ）＝２ｐ＋２」
pは奇素数でf(p)はmod pでフィボナッチ数列を見た時の周期を指す。
つまり、p=10^9+7なので、その時の周期は2*10^9+16である

今回はフィボナッチ数列を行列累乗で解くが、2回に分けて解く。
最初はmod 2*10^9+16で解く。
これで周期を意識したフィボナッチ数列での次の添字が取れる。

後は、その添字に対して、mod 10^9+7で改めてフィボナッチ数列を取れば良い。

ll N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    Fibonacci fib; // フィボナッチ数列をmod付きで取る
    ll M = fib.query(N, 2000000016LL);
    ll ans = fib.query(M, 1000000007);

    cout << ans << endl;
}

解説放送

前提知識

解法