斐波那契数列
问题 求斐波那契数列第$10^{19}$项的值，由于结果巨大，输出$mod$ $1000000007$的结果即可。 定义 前两项为1，从第三项开始都满足下面的公式 $$k_n = k_{n-1} + k_{n-2}$$ $$1,1,2,3,5,8,13\ldots$$ 简单的python实现 def fib(n): a = 0 b = 1 for _ in range(n): a, b = b, a + b return a 可以看出，上面算法的时间复杂度是$O(n)$，可以说是比较优的方式了，但是当我在我的电脑上运行上面的代码求第$10^{19}$次项的值时，它很久都没有给我运行结果。 需要使用到斐波那契Q矩阵来减少运算次数 先介绍一下快速幂运算的概念 $x^2 = x × x$ $x^4 = x^2 × x^2$ $x^{100} = x^{64} × x^{32} × x^4$ 观察上面的等式，$x^4$的计算如果用一次项乘4次需要计算3次，但是如果先计算2次项的平方则只需要计算2次。 同理，求$x^n$只需要计算$log2^n$次（实际操作是将低次项的结果保留起来，计算高次项时利用低次项的结果作为基础 ） 同时， $mod$运算也满足 $(A×B)\%C=(A\%C)×(B\%C)$ 使用幂运算的规则，所以只需要找到一个数或者表达式 $A$ 满足： $$k_n = A × k_{n-1}$$ 那么求第$n$项$fibonacci$值的问题就可以转化成求 $A^{n-1}$的问题了 但是通过$fibonacci$数列的定义可以知道，仅已知$k_{n-1}$无法确定$k_n$的值，必须要同时已知$k_{n-1}$和$k_{n-2}$才能确定$k_n$的值，即无法找到到 $A$ 满足$k_n = A × k_{n-1}$...