矩阵快速幂

概念讲解

核心思想

用矩阵表示线性递推关系，用快速幂加速计算。

矩阵乘法

1234567891011121314struct Matrix {
    long long a[2][2];
    Matrix operator*(const Matrix& other) const {
        Matrix result = {{{0,0},{0,0}}};
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    result.a[i][j] += a[i][k] * other.a[k][j];
                }
            }
        }
        return result;
    }
};

矩阵快速幂

123456789Matrix matrixPower(Matrix base, long long n) {
    Matrix result = {{{1,0},{0,1}}};  // 单位矩阵
    while (n > 0) {
        if (n & 1) result = result * base;
        base = base * base;
        n >>= 1;
    }
    return result;
}

应用

斐波那契数列

(F(n+1) F(n))=(11 10)n(1 0)\begin{pmatrix} F(n+1) \ F(n) \end{pmatrix} = \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \ 0 \end{pmatrix}

123Matrix base = {{{1,1},{1,0}}};
Matrix result = matrixPower(base, n);
return result.a[0][1];  // F(n)

时间复杂度：O(log⁡n)O(\log n)

考点分析

初赛考查方式

  1. 程序阅读： 矩阵快速幂
  2. 编程题： 递推优化

常见考点

  • 矩阵乘法
  • 矩阵快速幂
  • 构造转移矩阵

例题精讲

例题 1：斐波那契

题目： 求第 n 个斐波那契数。

解答：

使用矩阵快速幂，时间复杂度 O(log n)。

练习题

  1. 矩阵快速幂的时间复杂度是多少？
查看答案

O(k3log⁡n)O(k^3 \log n)

  • k 是矩阵的大小
  • n 是幂次
  • 每次矩阵乘法：O(k3)O(k^3)
  • 快速幂：O(log⁡n)O(\log n)

对于斐波那契数列，k=2，所以是 O(log⁡n)O(\log n)。

  1. 如何构造转移矩阵？
查看答案

构造转移矩阵的方法：

  1. 确定状态向量：将递推关系中的变量组成向量
  2. 找出转移关系：用矩阵表示状态之间的转移
  3. 验证：用小数据验证矩阵是否正确

例如斐波那契：
(F(n+1) F(n))=(11 10)(F(n) F(n−1))\begin{pmatrix} F(n+1) \ F(n) \end{pmatrix} = \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix} \begin{pmatrix} F(n) \ F(n-1) \end{pmatrix}

  1. 矩阵乘法满足交换律吗？
查看答案

不满足

A×B≠B×AA \times B \ne B \times A（一般情况下）

所以计算时要注意顺序，不能随意交换。

易错点

⚠️ 注意：

  1. 矩阵乘法不满足交换律
  2. 单位矩阵是对角线为 1
  3. 要用 long long 防溢出
  4. 构造转移矩阵是关键