---

快速幂

题目：计算 $x$ 的 $n$ 次幂 $x^n$（$n\ge 0$）。

当 $n$ 是负数时，可以先求 $x^{-n}$，再取倒数。

最简单的思路是直接进行 $n-1$ 次乘法。过程为 $x\to x^2\to x^3\to \cdots \to x^n$。

double normalPow(double x, int n){ if(n==0) return 1.0; double ans = x; for(int i=1; i<n; ++i) ans *= x; return ans; }

上面代码的时间复杂度是 $O(n)$，空间复杂度是 $O(1)$。

递归实现快速幂

快速幂算法的本质是分治算法：

想要计算 $x^n$，可以先递归地计算出 $y=x^{\lfloor n/2\rfloor }$。如果 $n$ 是偶数，$x^n=y^2$；否则，$x^n=y^2\cdot x$。递归的边界为 $n=0$，此时直接返回 1。 double quickPow(double x, int n){ if(n==0) return 1.0; double y = quickPow(x, n/2); double ans = y*y; if(n%2) ans *= x; return ans; }

时间复杂度是 $O(\lg n)$。 空间复杂度是 $O(\lg n)$，递归调用函数使用的栈空间。

迭代实现快速幂

以计算 $x^{43}$ 为例，43 的二进制表示为 00101011。

则有 $x^{43}=x^{1+2+8+32}=x^{2^0+2^1+2^3+2^5}=x^{2^0}\cdot x^{2^1}\cdot x^{2^3}\cdot x^{2^5}$。

一般地，如果整数 $n$ 的二进制拆分为 $n=2^{i_0}+2^{i_1}+\cdots +2^{i_k}$，那么 $x^n=x^{2^{i_0}}\times x^{2^{i_1}}\times \cdots \times x^{2^{i_k}}$。

因此，借助整数的二进制拆分，就可以得到迭代计算的方法： 从右向左遍历 $n$ 的二进制位，如果第 $i$ 个（从 0 开始计数）二进制位为 1，就将 $x^{2^i}$ 计入答案。

而 $x^{2^i}=x^{2\cdot 2^{i-1}}=(x^{2^{i-1}}{)}^2$，

根据上面的等式，可以计算 $x^{2^i}$ 的值：从 $x$ 开始不断地进行平方，得到 $x^2,x^4,x^8,x^{16},\cdots$，即 $x^{2^1},x^{2^2},x^{2^3},x^{2^4},\cdots$

double quickPow(double x, int n){ double ans = 1.0; while(n){ if(n&1) ans*=x; x *= x; n >>= 1; } return ans; }

时间复杂度是 $O(\lg n)$，对 $n$ 进行二进制拆分的时间。 空间复杂度是 $O(1)$。

---

矩阵快速幂

题目：计算斐波那契数列前 $n$ 项平方和，$n\ge 1$。为了防止答案过大，将最后的答案模 1e9+7。

斐波那契数列的推导式为 $F(n)=\{\begin{array}{ll}1,& n=1,2\\ F(n-1)+F(n-2),& n\ge 3\end{array}$

可以使用迭代直接计算：

const int MOD = 1e9+7; int squaredSumOfFibSequence(long long n){ if(n==1) return 1; if(n==2) return 2; long long sum = 2; long long pre1 = 1; long long pre2 = 1; for(long long i=3; i<=n; ++i){ long long cur = pre1 + pre2; sum += cur * cur; sum %= MOD; pre1 = pre2; pre2 = cur; } return (int)sum; }

上述代码的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

寻找规律

将 $F(i)$ 的值作为边长，那么 $F(i{)}^2$ 就是边长为 $F(i)$ 的正方形的面积。下图中，正方形中的数字表示它所在正方形的边长。

根据上图各矩形的边长和面积的关系，可以得出规律：${\sum }_{i=1}^{n}F(i{)}^2=F(n)\cdot F(n+1)$。

可以通过数学归纳法证明上述等式的正确性。

题目就转换成了求 $F(n)$ 和 $F(n+1)$ 的值。

最简单的思路是使用自底向上进行迭代的方法计算 $F(n)$ 的值：

const int MOD = 1e9+7; int fib(long long n){ if(n==1 || n==2) return 1; long long cur == 0; long long pre1 = 1; long long pre2 = 1; for(long long i=3; i<=n; ++i){ cur = pre1 + pre2; cur %= MOD; pre1 = pre2; pre2 = cur; } return (int)cur; }

上面代码的时间复杂度是 $O(n)$。

这样做就失去了进行上述转换的意义。因为相比直接计算平方和的代码，这没有对时间复杂度和空间复杂度有任何优化。

矩阵求幂

斐波那契数列矩阵方程：

$\left[\begin{array}{c}F(n+1)\\ F(n)\end{array}\right]=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\left[\begin{array}{c}F(n)\\ F(n-1)\end{array}\right]={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^{n-1}\left[\begin{array}{c}F(2)\\ F(1)\end{array}\right]$

矩阵的幂 ${\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^{n-1}$ 的计算可以使用快速幂算法。

C++代码实现如下：

#include<iostream> #include<cstring> using namespace std; const int MOD = 1e9+7; struct Matrix{ long long a[2][2]; Matrix(){ memset(a, 0, sizeof(a)); } }; // 矩阵相乘 AxB Matrix matrixMultiply(Matrix A, Matrix B) { Matrix C; for(int i=0; i<2; ++i){ for(int j=0; j<2; ++j){ for(int k=0; k<2; ++j){ C.a[i][j] += A.a[i][k] * B.a[k][j]; C.a[i][j] %= MOD; } } } return C; } // 计算矩阵 A 的 n 次幂。 // 矩阵的基本性质：乘法结合律 —— (AB)C = A(BC) Matrix matrixPower(Matrix A, long long n) { Matrix B; for(int i=0; i<2; ++i) B.a[i][i]=1; // 初始化为单位矩阵，如同数的乘法中的 1 while(n) { if(n&1) B = matrixMultiply(B, A); A = matrixMultiply(A, A); n >>= 1; } return B; } // 计算斐波那契数列前 n 项的平方和 int squaredSumOfFibSequence(long long n){ Matrix A; A.a[0][0] = 1; A.a[0][1] = 1; A.a[1][0] = 1; A.a[1][1] = 0; Matrix B = matrixPower(A, n); long long res1 = B.a[0][1]; // F(n)的值 Matrix C = matrixMultiply(B, C); long long res2 = C.a[0][1]; // F(n+1)的值 long long ans = res1 * res2 % MOD; return (int)ans; } int main(){ long long n; cin >> n; cout << "斐波那契数列前 n 项的平方和（模 1e9+7）：" << squaredSumOfFibSequence(n) << endl; return 0; }

时间复杂度是 $O(\lg n)$，对 $n$ 进行二进制拆分的时间。 空间复杂度是 $O(1)$。

---

刷题题解目录