矩阵快速幂：用积木搭出超级次方

它是谁？用来干什么？

矩阵快速幂是一种算法，它结合了“矩阵乘法”和“快速幂”两个技巧，能飞快地算出矩阵的高次幂。比如你要算 矩阵A的100次方，如果用普通方法乘99次，计算机可能会累哭；但矩阵快速幂只需要乘大约 log₂(100) ≈ 7 次，快得像“复制粘贴”。

它的用途很广：计算斐波那契数列的第n项、求图的路径条数、解线性递推……很多问题只要写成矩阵形式，就能用这个“加速器”瞬间解决。

1. 矩阵乘法——像搭积木一样“拼”在一起

还记得你玩过的积木吗？一块积木是正方形，两块积木可以拼成更大的长方形。矩阵乘法也是这种“拼合”的操作——两个矩阵相乘，得到一个新矩阵。

乘法规则（2×2矩阵为例）

假设有两个2×2的矩阵A和B：

A = [a b]    B = [e f]
    [c d]        [g h]

它们的乘积 C = A × B 是这样算的：

C[0][0] = a×e + b×g    （第一行×第一列）
C[0][1] = a×f + b×h    （第一行×第二列）
C[1][0] = c×e + d×g    （第二行×第一列）
C[1][1] = c×f + d×h    （第二行×第二列）

简单说：新矩阵的每个元素，都是左边矩阵的一行与右边矩阵的一列对应相乘再相加。

生活小例子

想象你有一张 “翻倍卡” 和一张 “加一卡”，它们分别对应两个矩阵：

翻倍卡：[2 0; 0 2]（把数字扩大两倍）
加一卡：[1 1; 0 1]（给数字加1）

如果你先用翻倍卡，再用加一卡，效果就是两个矩阵的乘积，结果矩阵代表“先翻倍再加一”的整体变换。这就是矩阵乘法在生活中的含义——把两个变换合并成一个。

2. 快速幂的思想——用“平方”省力气

从数字开始

假如要算 2的10次方，你可以一个个乘：2×2×2×... 要乘9次。但聪明的小朋友会发现：

2^10 = (2^5)^2
2^5  = (2^2)^2 × 2

实际上，我们只需要这样算：

先算 2^2 = 4（1次乘法）
再算 (2^2)^2 = 4^2 = 16（1次乘法），此时得到2^4
再乘一次2得到2^5（1次乘法）
最后平方 (2^5)^2 = 32^2 = 1024（1次乘法）

总共只需要4次乘法，比9次少得多。这就是快速幂的核心——把指数拆成二进制，用平方和乘法代替连续乘法。

二进制视角

看指数10的二进制是 1010：

从低位到高位，遇到1就乘当前底数，底数每次都平方。
初始结果 = 1（单位元），底数 = 2。
第一步：位=0，底数平方为4，结果不变。
第二步：位=1，结果乘底数（当前底数是4）→ 结果=4，底数平方为16。
第三步：位=0，底数平方为256。
第四步：位=1，结果乘底数（当前底数是256）→ 结果=4×256=1024。

看，只需处理4位，乘法次数不超过2×位数。这个思想对任何“能相乘的东西”都成立，矩阵也不例外。

3. 把矩阵也当成数字——矩阵快速幂

既然矩阵乘法满足结合律（和数字乘法一样），我们就可以把快速幂的思想直接用在矩阵上。

关键三部曲

单位矩阵：数字乘法中的“1”对应矩阵中的 单位矩阵（主对角线全是1，其余是0）。任何矩阵乘以单位矩阵还是它自己。
矩阵乘法：需要自己写一个函数，把两个矩阵乘起来。
二进制分解：用while循环，每次判断指数的最低位，如果最低位是1就乘上当前矩阵，然后当前矩阵平方，指数右移一位。

复杂度对比

普通方法：需要 n-1 次矩阵乘法，复杂度 O(n)。
快速幂：需要 O(log n) 次矩阵乘法，当 n 很大时（比如10^18），优势巨大。

4. 完整代码示例：用矩阵快速幂求斐波那契数列

斐波那契数列满足：F₀=0, F₁=1, Fₙ = Fₙ₋₁ + Fₙ₋₂。我们可以用矩阵表示：

[Fₙ  ]   = [1 1]^(n-1) × [F₁]   = [1 1]^(n-1) × [1]
[Fₙ₋₁]     [1 0]         [F₀]     [1 0]         [0]

所以只要算出 [1 1; 1 0] 的 n-1 次方，结果矩阵左上角就是 Fₙ。

#include <iostream>
#include <vector>
using namespace std;

// 定义矩阵类型：2x2的二维数组
typedef vector<vector<int>> Matrix;

// 矩阵乘法函数，计算A*B
Matrix mul(Matrix A, Matrix B) {
    // 初始化结果矩阵为2x2全0
    Matrix C(2, vector<int>(2, 0));
    for (int i = 0; i < 2; i++)          // 行
        for (int j = 0; j < 2; j++)      // 列
            for (int k = 0; k < 2; k++)  // 中间求和
                C[i][j] += A[i][k] * B[k][j];
    return C;
}

// 矩阵快速幂函数：计算A的n次方
Matrix pow(Matrix A, int n) {
    // 单位矩阵，相当于数字1
    Matrix result = {{1, 0}, {0, 1}};
    while (n > 0) {
        if (n % 2 == 1)            // n是奇数，需要乘上当前A
            result = mul(result, A);
        A = mul(A, A);             // A自乘：底数平方
        n /= 2;                    // 去掉最低位
    }
    return result;
}

int main() {
    int n = 10;                     // 求第10项（从0开始：F0=0, F1=1）
    Matrix base = {{1, 1}, {1, 0}}; // 斐波那契矩阵
    // 注意：要得到F_n，需要base的n-1次方
    Matrix M = pow(base, n - 1);
    // 结果矩阵的第一行第一列就是F_n
    cout << "Fibonacci第" << n << "项是: " << M[0][0] << endl;
    return 0;
}

运行结果：Fibonacci第10项是: 55

5. 另一个生活例子：计算存钱罐的增长

假设你有一个存钱罐，第一天有1元，之后每天的钱数是前一天的两倍再加上1元。即：

a₁ = 1
aₙ = 2 × aₙ₋₁ + 1

这可以用矩阵表示：

[aₙ  ] = [2 1]^(n-1) × [a₁] = [2 1]^(n-1) × [1]
[  1 ]   [0 1]         [ 1]   [0 1]         [1]

用同样的矩阵快速幂，就能算出第100天的钱数。如果直接递推要算99次，而快速幂只需约7次矩阵乘法。

6. 新手容易犯的错误

❌ 错误1：忘记初始化结果为单位矩阵

很多新手把结果矩阵初始化为全0，结果乘任何矩阵都是0。记住：乘法中的“1”是单位矩阵。

❌ 错误2：矩阵乘法中循环顺序写错

常见写法是 for(i) for(j) for(k)，但有人会误写成 for(i) for(k) for(j)，虽然结果一样（因为加法交换），但为了清晰，建议保持行列顺序。

❌ 错误3：指数为0的情况

任何矩阵的0次方应该是单位矩阵。如果代码中 while(n>0) 不加处理，n=0时不会进入循环，直接返回初始化的result。所以要确保result初始化为单位矩阵。

❌ 错误4：数据类型溢出

矩阵元素可能很大（比如斐波那契第100项超过int范围）。建议用 long long 或定义模数，竞赛中常用 const int MOD = 1e9+7 并取模。

❌ 错误5：斐波那契中n-1次方容易搞错

直接求 base^n 得到的是 F_{n+1}，注意矩阵递推的起点，可以画一下前几项验证。

7. 总结与更多指引

矩阵快速幂就像用“复制粘贴”代替“逐个拼积木”，让原本需要成千上万次计算的难题，瞬间就能解决。即使你还小，只要记住这个思想，以后学更深的算法就会轻松很多。

接下来可以学什么？

矩阵乘法的更多性质：比如结合律、分配律，为快速幂打基础。
快速幂的其他应用：整数快速幂、模快速幂（密码学常用）。
线性递推：任何形如 f(n) = a1*f(n-1) + a2*f(n-2) + ... 的递推式都可以用矩阵快速幂优化。
图论：路径计数：邻接矩阵的k次幂的第i行第j列就是i到j长度为k的路径条数。
动态规划优化：很多DP方程可以写成矩阵形式，用快速幂加速。

如果你喜欢挑战，可以尝试求 F_{10^18} 模一个大质数，看看矩阵快速幂的威力！

例题精讲