数列"/>

快速幂求解斐波那契数列

斐波那契数列

斐波那契数列是很经典也很简单的一条题目。其满足：
F n = { 1 ( n ≤ 2 ) F n − 1 + F n − 2 ( n ≥ 3 ) F_{n}= \begin{cases}1 & (n \leq 2) \\ F_{n-1}+F_{n-2} & (n \geq 3)\end{cases} Fn​={1Fn−1​+Fn−2​​(n≤2)(n≥3)​
请求出 F n m o d 1 0 9 + 7 F_{n} \bmod 10^{9}+7 Fn​mod109+7的值。

递归和顺序求解

最简单的方法便是递归和顺序求解。递归的时间复杂度为 O ( 2 n ) O(2^n) O(2n)，顺序求解的复杂度为 O ( n ) O(n) O(n)。这里不再贴代码了。

快速幂

那有没有比 O ( n ) O(n) O(n)更快的方法呢。是有的。快速幂的最基础应用便是求一个数的 n n n次方。比如我们要求 1 1 10 11^{10} 1110。如果一次一次乘，那么需要九次乘法。如果先算11的五次方，再求平方，那么便需要五次乘法。那先计算 11 ∗ 11 = 121 11*11=121 11∗11=121，那么11的五次方便是 121 ∗ 121 ∗ 11 121*121*11 121∗121∗11，再平方，最后一共用了四次乘法。有没有发现，拆解的越多，乘法的次数就越少，那么采用二分的思想，便可实现 O ( l o g 2 n ) O(log_2n) O(log2​n)时间复杂度的求幂次方。
刚才的二分想法的递归方程不难理解，如下：
a n = { a n − 1 ⋅ a , if  n is odd  a n 2 ⋅ a n 2 , if  n is even but not  0 1 , if  n = 0 a^{n}= \begin{cases}a^{n-1} \cdot a, & \text { if } n \text { is odd } \\ a^{\frac{n}{2}} \cdot a^{\frac{n}{2}}, & \text { if } n \text { is even but not } 0 \\ 1, & \text { if } n=0\end{cases} an=⎩⎪⎨⎪⎧​an−1⋅a,a2n​⋅a2n​,1,​ if n is odd  if n is even but not 0 if n=0​
代码也很简单：

int qpow(int a, int n)
{if (n == 0)return 1;else if (n % 2 == 1)return qpow(a, n - 1) * a;else{int temp = qpow(a, n / 2);return temp * temp;}
}

需要注意的是，这里的temp变量是需要的，如果直接“return qpow(a, n/2)*qpow(a, n/2)”，那其实会计算两次qpow(a, n/2)，时间复杂度退化到了 O ( n ) O(n) O(n)。
递归会有额外空间开销，我们可以用循环的方式写，代码如下：

int qpow(int a, int n){int ans = 0;while (n){if (n & 1){ans *= a; }a *= 1;n >> 1;}return ans;
}

按照上面 1 1 10 11^{10} 1110的例子，这个循环就是将其拆成 1 1 10 = 1 1 8 + 1 1 2 11^{10} = 11^8 + 11^2 1110=118+112。通过不断的“n >> 1”来获取当前n二进制最后一个1。

快速幂求解斐波那契

下面就是最关键的部分了。
设矩阵 A = [ 0 1 1 1 ] A=\left[\begin{array}{ll}0 & 1 \\ 1 & 1\end{array}\right] A=[01​11​]，有 A [ F n F n + 1 ] = [ F n + 1 F n + F n + 1 ] = [ F n + 1 F n + 2 ] A\left[\begin{array}{c}F_{n} \\ F_{n+1}\end{array}\right]=\left[\begin{array}{c}F_{n+1} \\ F_{n}+F_{n+1}\end{array}\right]=\left[\begin{array}{c}F_{n+1} \\ F_{n+2}\end{array}\right] A[Fn​Fn+1​​]=[Fn+1​Fn​+Fn+1​​]=[Fn+1​Fn+2​​]，那么：
[ F n F n + 1 ] = A [ F n − 1 F n ] = A 2 [ F n − 2 F n − 1 ] = … = A n − 1 [ F 1 F 2 ] = A n − 1 [ 1 1 ] \begin{aligned} {\left[\begin{array}{c} F_{n} \\ F_{n+1} \end{array}\right] } &=A\left[\begin{array}{c} F_{n-1} \\ F_{n} \end{array}\right] \\ &=A^{2}\left[\begin{array}{l} F_{n-2} \\ F_{n-1} \end{array}\right] \\ &=\ldots \\ &=A^{n-1}\left[\begin{array}{l} F_{1} \\ F_{2} \end{array}\right] \\ &=A^{n-1}\left[\begin{array}{l} 1 \\ 1 \end{array}\right] \end{aligned} [Fn​Fn+1​​]​=A[Fn−1​Fn​​]=A2[Fn−2​Fn−1​​]=…=An−1[F1​F2​​]=An−1[11​]​

原来的求第n个斐波那契数列的值，变成了矩阵的n-1次方。代码如下：

#include <iostream>
using namespace std;
typedef long long ll; //由于数可能很大，所以采用long long。
const ll MOD = 1000000007;struct matrix
{ll a1, a2, b1, b2;matrix(ll a1, ll a2, ll b1, ll b2) : a1(a1), a2(a2), b1(b1), b2(b2) {}matrix operator * (const matrix& y) //重载*，适应矩阵乘法{matrix ans((a1 * y.a1 + a2 * y.b1) % MOD,(a1 * y.a2 + a2 * y.b2) % MOD,(b1 * y.a1 + b2 * y.b1) % MOD,(b1 * y.a2 + b2 * y.b2) % MOD); // 矩阵乘法，同时防止数过大，取余.return ans;}
};matrix qpow(matrix a, ll n) //套用快速幂模板
{matrix ans(1, 0, 0, 1); //单位矩阵while (n){if (n & 1)ans = ans * a;a = a * a;n >>= 1;}return ans;
}int main()
{ll n;matrix A(0, 1, 1, 1);  //上述证明中的A矩阵。cin >> n;matrix ans = qpow(A, n - 1);cout << ans.a1 + ans.a2 % MOD;system("pause");return 0;
}

快速幂模板

斐波那契数列只是快速幂用于矩阵幂次方求解的应用，快速幂还是可以用于很多地方，都可以套用模板，代码如下：

//泛型的非递归快速幂
template <typename T>
T qpow(T a, ll n)
{T ans = 1; // 赋值为乘法单位元，可能要根据构造函数修改while (n){if (n & 1)ans = ans * a; // 这里就最好别用自乘了，不然重载完*还要重载*=，有点麻烦。n >>= 1;a = a * a;}return ans;
}