行列のできるフィボナッチ数列道場 (1) [yukicoder No.718]

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

考察過程

1. 特殊な規則性があるのではないかということでN=1～100を作ってみる
2. パッと見てみるとさっぱり分からない
3. フィボナッチ数列は特殊な公式が多いので、ググる
4. ある
5. 行列累乗を使えば、フィボナッチ数列のある項はすぐ求められるので、解けた

前提知識

• 行列累乗でフィボナッチ数列の任意の項を高速に求めるテク

解法

https://yukicoder.me/submissions/275464

ぐぐると、こういうものがある。
なので、フィボナッチ数列のN項とN+1項が求まれば答えが求められる。
　
フィボナッチ数列の任意の項を高速に求めるには行列累乗を使う方法が知られている。
自分はこれをライブラリ化しているので、持ってきて貼っている。
以下のコードはだいぶライブラリに頼っているので、あまり参考にならないかもしれない。

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

    Fibonacci f;
    mint fn = f.query(N);
    mint fn1 = f.query(N + 1);
    
    mint ans = fn * fn1;
    cout << ans << endl;
}