矩阵快速幂CSP-S

💡 核心思想

矩阵快速幂是将快速幂的思想推广到矩阵乘法。当递推式可以表示为线性变换时（如 fib[n] = fib[n-1] + fib[n-2]），可以构造转移矩阵，通过矩阵快速幂在 O(k³ log n) 时间内计算第 n 项，其中 k 为矩阵维度。经典应用：斐波那契数列、线性递推、图上固定步数的走法计数。

🎯 直觉理解

想象你在爬楼梯，每次可以跨 1 步或 2 步。问爬到第 100 层有多少种方法？普通做法是逐个算，但矩阵快速幂就像"坐火箭"：它把"跨一步"和"跨两步"的规则打包成一个"传送矩阵"，然后直接算这个矩阵的 100 次方，一步到位。

📝 算法流程

1. 写出递推式的向量形式
2. 构造 k×k 的转移矩阵 T
3. 初始向量 V₀
4. Vₙ = Tⁿ × V₀
5. 用快速幂计算 Tⁿ，时间 O(k³ log n)
6. 经典转移矩阵：斐波那契 [[1,1],[1,0]]

$$\begin{pmatrix} f_n \\ f_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} f_{n-1} \\ f_{n-2} \end{pmatrix}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;

struct Matrix {
    ll a[2][2];
    Matrix() { memset(a, 0, sizeof(a)); }
    Matrix operator*(const Matrix& o) const {
        Matrix res;
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                for (int k = 0; k < 2; k++)
                    res.a[i][j] = (res.a[i][j] + a[i][k] * o.a[k][j]) % MOD;
        return res;
    }
};

Matrix qpow(Matrix base, ll n) {
    Matrix res;
    res.a[0][0] = res.a[1][1] = 1; // 单位矩阵
    while (n) {
        if (n & 1) res = res * base;
        base = base * base;
        n >>= 1;
    }
    return res;
}

ll fib(ll n) {
    if (n <= 1) return n;
    Matrix T;
    T.a[0][0] = T.a[0][1] = T.a[1][0] = 1; T.a[1][1] = 0;
    Matrix R = qpow(T, n - 1);
    return R.a[0][0]; // fib[n]
}

int main() {
    cout << fib(10) << endl;  // 55
    cout << fib(50) << endl;  // 12586269025 % MOD
    return 0;
}

⚠️ 常见坑点

📚 相关题目