yukicoder - No.147 試験監督(2)をそこそこ高速に解く
リンクについてる解説が結構どれもTLEが厳しそうでしたが、300msぐらいで通ります。
解説
フィボナッチ数列になるのは他の解説を参考にしてください。
ここまでくると求めるのは
になります。
フィボナッチ数列は普通に行列累乗で求めても高速に求まりますが、一工夫あって実はmod 1'000'000'007では周期が2 * (1'000'000'007 + 1)であることが知られています。
詳しくは
ということで、まずはCを2 * (1'000'000'007 + 1)で割った余りにしてしまいましょう。
次はDに関してですが、フェルマーの小定理から,、が1'000'000'007と互いに素なら
です。よってフィボナッチ数列の番目を1'000'000'007で割った余りが0なら0で、そうでないならは1'000'000'006で割った余りでやれば大丈夫です。
以上で高速に求めることができました。