はまやんはまやんはまやん

hamayanhamayan's blog

フィボナッチフィボナッチ数 [yukicoder No.534]

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

解法

https://yukicoder.me/submissions/183423

このページにこんな一節がある。
「p=±2(mod5)のとき,f(p)=2p+2」
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;
}