突发奇想想到的。

根据斐波那契数列的递推式 $Fib_i=Fib_{i-1}+Fib_{i-2}$，我们令 $x^2 = x + 1$。
在求解 $Fib_n$ 时，我们将 $x^n$ 根据上方等式进行降次，最终会得到一个一次式子，一次项系数即为 $Fib_n$。

然后由于最后降次之后只有两项，这个东西可以快速幂 $O(\log n)$ 求出来。一份提交记录

有两个疑问：

• 关于这个方法的正确性我现在只能感性理解，没法给出严谨证明，求做法正确性证明
• 这个做法跟矩阵快速幂的联系在哪里，能不能拓展到其他数列

本人太蒻了，求解答 /bx