专题进阶 · 数学算法推荐总顺序 · 第 111 / 148 课

把线性递推写成状态转移矩阵,再用二进制幂跨过大量步数。

先学会这些,再进入本课 快速幂 矩阵乘法 一维 DP
还有 3 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 数学算法

矩阵快速幂Matrix Exponentiation

把线性递推表示成状态矩阵,再用二进制幂加速跨越大量步骤。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

把线性递推写成状态转移矩阵,再用二进制幂跨过大量步数。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

F₀=0、F₁=1、Fₙ=Fₙ₋₁+Fₙ₋₂,要计算很大的 n,能否不逐项填 n 个状态?

02一步步得到方法

把需要记住的状态放进向量

令 sₖ=[Fₖ₊₁,Fₖ]ᵀ,则 sₖ₊₁=[[1,1],[1,0]]·sₖ。第一行把前两项相加,第二行把原第一项向下搬移。矩阵的每一行都对应下一状态的一条计算规则。

反复 n 次就是 sₙ=Mⁿs₀,s₀=[1,0]ᵀ。矩阵乘法有结合律,因此可用快速幂;不需要交换律,只要乘法顺序保持正确。

适用范围是固定线性转移

若递推包含 max、非线性函数或每步使用不同矩阵,不能直接套一个固定 M 的幂。可扩展常数项时增加一个恒为 1 的状态分量,但应先逐项验证矩阵乘出来的式子。

指数 0 返回单位矩阵 I,因为不推进状态。矩阵尺寸 d 决定一次乘法成本,不能仅写 O(log n) 而省掉 d³。

状态向量的方向决定矩阵写法

先规定状态用列向量还是行向量。例如列向量 [F(n+1),F(n)]ᵀ 左乘转移矩阵得到下一状态;换成行向量时矩阵位置和索引也要相应调整。

重复相同线性转移才等价于矩阵幂。若每一步矩阵随时间变化,不能简单求某个固定矩阵的 k 次幂;零次幂应是单位矩阵,保证不执行转移时原状态不变。

03把一个小例子完全算清楚

M=[[1,1],[1,0]],求 F₅。

步骤计算与状态为什么这样做
M²[[2,1],[1,1]]推进两步
M⁴[[5,3],[3,2]]再次平方
M⁵=M⁴M[[8,5],[5,3]]取第 0 行第 1 列得 5

窄屏可左右滑动表格,阅读完整计算与理由。

F₅=5;矩阵还同时保留了相邻 Fibonacci 项的信息。

04为什么这个方法成立

  1. 一阶转移矩阵按行准确实现下一状态公式。
  2. 矩阵幂的乘法次数合成相应步数。
  3. 快速幂不变量保持累计矩阵与剩余幂的乘积为目标 Mⁿ,结束后得到准确转移。

05把推导翻译成代码

Python · 可独立运行的教学实现

def multiply(a,b):
    return [[sum(a[i][k]*b[k][j] for k in range(len(b)))
             for j in range(len(b[0]))] for i in range(len(a))]
def matrix_power(a,n):
    assert n >= 0 and all(len(row)==len(a) for row in a)
    size = len(a)
    result = [[int(i==j) for j in range(size)] for i in range(size)]
    while n:
        if n & 1:
            result = multiply(result,a)
        a = multiply(a,a)
        n //= 2
    return result
def fibonacci(n):
    return matrix_power([[1,1],[1,0]],n)[0][1]

逐个理解关键决定

int(i==j)
构造单位矩阵,主对角线为 1,其他为 0。
multiply(result,a)
矩阵乘法不交换,保持累积方向,不按标量直觉任意换顺序。

06时间、空间与实现范围

普通 d×d 矩阵乘法 O(d³),总 O(d³ log(n+1)),矩阵工作存储 O(d²)。

Fibonacci 本身有指数增长的数值,若不取模,大整数乘法不能视为常数;常见应用在每次乘加后按指定模数取模。

07改变条件,检查哪里会出错

把 F₀、F₁ 的状态顺序写反

先实际乘一次,检查输出是否确实变为 [F₂,F₁]。

把矩阵元素逐项求幂

A² 表示 A×A 的矩阵乘法,通常完全不同于每个元素平方。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

n=0 返回什么矩阵?

需要一点提示

零次转移。

查看解析与答案

单位矩阵,F₀ 对应非对角元素 0。

练习 2 · 边界与辨析

Fₙ=2Fₙ₋₁+3Fₙ₋₂ 的转移矩阵?

需要一点提示

第一行写系数,第二行搬移。

查看解析与答案

[[2,3],[1,0]],状态顺序保持 [Fₖ₊₁,Fₖ]。

练习 3 · 变式与迁移

如果递推每步还加 5 怎么扩展?

需要一点提示

增加恒定分量。

查看解析与答案

使用 [Fₖ₊₁,Fₖ,1]ᵀ,第一行 [2,3,5],第二行 [1,0,0],第三行 [0,0,1]。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

CP-Algorithms · 欧几里得与最小公倍数CP-Algorithms · 二进制快速幂

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。