深夜的快递分拣中心里，传送带永不停歇。主管发现一条铁律：今天要处理的包裹量，完全由前几天的数据决定——“今天 = 昨天 × 2 + 前天 × 3”。这套规则一旦定下，只要翻出过去几天的报表，就能预言未来任何一天的工作量。数学上，这条铁律叫做常系数线性递推，斐波那契数列正是它最出名的“招牌订单”。问题是：想算第 10 亿天的包裹量，难道要沿着传送带跑 10 亿圈？数学家发明了三条捷径：把规则装进矩阵、用快速幂跳级、用特征方程与生成函数直接写出通项。本文就从传送带的第一节开始，带你亲手打造这台“时间穿梭机”。

岗位关联

学会用矩阵快速幂解递推，你就能在算法竞赛、大规模数值计算与动态规划优化中，把 O(n) 的线性递推压缩到 O(log n)——这是算法工程师与高性能计算从业者的核心基本功。

目录
  1. 可视化演示
  2. 递推关系入门
  3. 矩阵表示构造
  4. 矩阵快速幂
  5. 特征方程法
  6. 生成函数法
  7. 优化与扩展
  8. 动态规划应用
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

本节配有交互动效（进入视口后自动加载，约 3KB）。

递推关系入门

在快递分拣中心，传送带旁贴着一张永不更换的“生产规则”：今天处理的包裹量，等于昨天量的 3 倍加上前天量的 2 倍。车间主任不必等今天开工，只要翻出前两天的报表，就能提前调度人力。这条规则有三个鲜明的性格：一是今天永远只看昨天和前天；二是系数 3 和 2 从不改变；三是每天都机械地照同一张配方执行。

数学家把这类“用过去的几个值算出下一个值”的规则称为递推关系。系数固定不变，叫常系数；每个依赖项都只出现一次方、没有互相相乘，叫线性。最出名的招牌配方当属斐波那契：本月 = 上月 + 上上月，从一对兔子繁殖问题演化成了整个数学界的明星数列。

形式化地说，一个 k 阶常系数线性递推由 k 个初值加上一条规则组成：

传送带的第一节就是这么简单：记住这条规则，接下来我们要研究的是——如何不沿传送带一步步走，直接“穿梭”到第 10 亿天。

an=c1an−1+c2an−2+⋯+ckan−k\displaystyle a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}
  1. 输出项 a_n$a_n$ 表示序列中第 $n$ 个值，也就是传送带上“今天”的包裹量，是递推要计算的目标。
    ana_n
  2. 常系数 c_i每个 $c_i$ 都是固定常数，不随 $n$ 变化——正是“常系数”的含义，如同生产规则一旦定下就绝不更改。
    c1,c2,…,ck∈Rc_1, c_2, \ldots, c_k \in \mathbb{R}
  3. 线性加权和右端只是把前 $k$ 项分别乘以系数再相加，没有 $a_i a_j$ 这类高阶项，所以是线性的。
    c1an−1+c2an−2+⋯+ckan−kc_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}
  4. 阶数与初值$k$ 表示递推依赖最近多少个值；要启动它，得像开机前补填报表一样，先给定前 $k$ 项。
    a0,a1,…,ak−1 给定a_0, a_1, \ldots, a_{k-1} \ \text{给定}

矩阵表示构造

主管很快发现，单独盯一个数字效率太低。于是他把最近几天的报表打包成一个“货柜”，每格放一天的数据，整个货柜随传送带前进。这个货柜在数学里叫状态向量：把最近 $k$ 个值竖着排成一列。

光有货柜还不够，还要配一份“操作手册”——每次流转时，新货柜的内容如何由旧货柜算出。手册被整理成一张方正的表格，称为转移矩阵：第一行写着生产规则的系数，左下角的斜线上排着一串 1，其余位置全是 0。

有了货柜和手册，流水线可以正式开跑了。但主管马上想到：跑 $n$ 步就要执行 $n$ 次矩阵乘法，跟原来一步步算有什么区别？好戏在后面——让传送带学会“跳级”。

[anan−1⋮an−k+1]=[c1c2⋯ck−1ck10⋯0001⋯00⋮⋮⋱⋮⋮00⋯10][an−1an−2⋮an−k]\displaystyle \begin{bmatrix} a_n \\ a_{n-1} \\ \vdots \\ a_{n-k+1} \end{bmatrix} = \begin{bmatrix} c_1 & c_2 & \cdots & c_{k-1} & c_k \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \end{bmatrix} \begin{bmatrix} a_{n-1} \\ a_{n-2} \\ \vdots \\ a_{n-k} \end{bmatrix}
  1. 状态向量封装左边 $\vec{v}_n$ 是“今天”的货柜，装着最近 $k$ 个值，维度等于递推阶数。
    v⃗n=[anan−1⋯an−k+1]T\vec{v}_n = \begin{bmatrix} a_n & a_{n-1} & \cdots & a_{n-k+1} \end{bmatrix}^{\mathsf{T}}
  2. 首行写系数矩阵第一行第 $j$ 列放 $c_j$，保证新首项确实是老首项的线性加权。
    M1,j=cj(1≤j≤k)M_{1,j} = c_j \quad (1 \le j \le k)
  3. 次对角线放 1第二行起的 $M_{i+1,i} = 1$ 让旧货柜内容整体“上移一格”，实现顺位传递。
    Mi+1,i=1(1≤i≤k−1)M_{i+1,i} = 1 \quad (1 \le i \le k-1)
  4. 一步一更新$\vec{v}_n = M \vec{v}_{n-1}$ 表示传送带每走一步，货柜内容就按手册刷新一次。
    v⃗n=Mv⃗n−1\vec{v}_n = M \vec{v}_{n-1}

矩阵快速幂

主管盯着一长串传送带沉思：如果 13 次流转可以拆成“8 圈 + 4 圈 + 1 圈”三组，而每一组又能预先“合并”成一个超级动作，那不只需要执行 3 次了吗？这正是二进制分解的直觉：把大步数拆成 2 的幂，分别合并，再挑需要的组合。

数学上，$n$ 次流转就是矩阵 $M$ 自乘 $n$ 次，记为 $M^n$。关键在于幂运算法则：$M^a \times M^b = M^{a+b}$。把 $n$ 写成二进制，$M^n$ 就变成若干“预制”的 2 的幂矩阵相乘。

“时间穿梭引擎”就此诞生：原来要沿着传送带跑 $n$ 圈，现在只做约 $\log_2 n$ 次矩阵乘法。引擎装好了，工程师们还想搞懂传送带的“脾气”——这就是特征方程。

Mn=Mb020×Mb121×⋯×Mbm2m,n=b020+b121+⋯+bm2m\displaystyle M^{n} = M^{b_0 2^0} \times M^{b_1 2^1} \times \cdots \times M^{b_m 2^m}, \qquad n = b_0 2^0 + b_1 2^1 + \cdots + b_m 2^m
  1. 二进制拆指数把 $n$ 摊成 2 的幂之和，每个 $b_i$ 取 0 或 1，例如 $13 = 8 + 4 + 1$。
    n=∑i=0mbi2i,bi∈{0,1}n = \sum_{i=0}^{m} b_i 2^i, \quad b_i \in \{0, 1\}
  2. 幂的乘法法则同底数幂相乘、指数相加，于是 $M^8 M^4 M^1 = M^{13}$，组合方式与二进制位一一对应。
    Ma×Mb=Ma+bM^a \times M^b = M^{a+b}
  3. 迭代平方从 $M^{2^0} = M$ 开始，每次自乘得到下一阶 $M^{2^{j+1}} = (M^{2^j})^2$，共约 $\log_2 n$ 次乘法。
    M2j+1=(M2j)2M^{2^{j+1}} = \left(M^{2^j}\right)^2

特征方程法

主管好奇：能不能不搬货柜，直接写出第 $n$ 天的包裹量公式？他把递推规则“输入”到一个称为特征方程的代数方程里，就像给传送带做一次“频率体检”，测出它固有的节拍。

方法很优雅：先假设某一项可以写成 $a_n = \lambda^n$ 的指数形式，代入递推式后两边约掉公共因子，就得到关于 $\lambda$ 的多项式方程。解出全部特征根后，把不同“节拍”按初值叠加，便得到通项公式。

有了“频率指纹”，任何一天的值都能用一行公式算出来。但特征法需要解多项式方程，阶数一高并不轻松——于是“档案袋”方法登场。

xk−c1xk−1−c2xk−2−⋯−ck=0an=A1λ1n+A2λ2n+⋯+Akλkn\displaystyle \begin{aligned} x^k - c_1 x^{k-1} - c_2 x^{k-2} - \cdots - c_k &= 0 \\[4pt] a_n &= A_1 \lambda_1^n + A_2 \lambda_2^n + \cdots + A_k \lambda_k^n \end{aligned}
  1. 指数型试探解设 $a_n = \lambda^n$ 代入递推式并消去公因子 $\lambda^{n-k}$，得到特征方程。
    λn=c1λn−1+⋯+ckλn−k  ⇒  xk−∑i=1kcixk−i=0\lambda^n = c_1 \lambda^{n-1} + \cdots + c_k \lambda^{n-k} \;\Rightarrow\; x^k - \sum_{i=1}^{k} c_i x^{k-i} = 0
  2. 解出特征根这是 $k$ 次代数方程，共有 $k$ 个根 $\lambda_1, \ldots, \lambda_k$（允许复数）。
    xk−c1xk−1−⋯−ck=(x−λ1)(x−λ2)⋯(x−λk)x^k - c_1 x^{k-1} - \cdots - c_k = (x - \lambda_1)(x - \lambda_2) \cdots (x - \lambda_k)
  3. 线性叠加通项每个根贡献一项 $A_i \lambda_i^n$，组合系数由 $k$ 个初值解线性方程组确定。
    an=∑i=1kAiλina_n = \sum_{i=1}^{k} A_i \lambda_i^n
  4. 重根修正若 $\lambda$ 是 $r$ 重根，对应项改为多项式乘指数，保证仍能凑出 $k$ 个线性无关解。
    (A0+A1n+⋯+Ar−1nr−1)λn\left(A_0 + A_1 n + \cdots + A_{r-1} n^{r-1}\right) \lambda^n

生成函数法

还有一种打包思路更极端：把整条无限长的传送带“拍一张缩略图”——把序列 $a_0, a_1, a_2, \ldots$ 分别作为 $x^0, x^1, x^2, \ldots$ 的系数，装进一个形式幂级数 $F(x)$。这个档案袋只有一个变量 $x$，却压缩了全部历史记录。

关键操作是“用递推规则折叠档案袋”：把 $F(x)$ 减去平移后的各项，递推关系会让绝大多数项互相抵消，最终得到紧致的封闭形式——一个分子是多项式、分母编码递推规则的有理函数。

档案袋与特征方程其实是一对孪生兄弟：分母的根恰恰就是特征根。它更适合理论推导，而工程上真正日复一日的还是矩阵快速幂。接下来给传送带减负。

F(x)=∑n=0∞anxn=P(x)1−c1x−c2x2−⋯−ckxk\displaystyle F(x) = \sum_{n=0}^{\infty} a_n x^n = \frac{P(x)}{1 - c_1 x - c_2 x^2 - \cdots - c_k x^k}
  1. 装配档案袋把每个 $a_n$ 挂在 $x^n$ 旁边，整个数列被编码进一个幂级数。
    F(x)=a0+a1x+a2x2+⋯F(x) = a_0 + a_1 x + a_2 x^2 + \cdots
  2. 分母写规则用递推系数拼出分母 $1 - c_1 x - \cdots - c_k x^k$，它决定了档案袋的“结构骨架”。
    1−c1x−c2x2−⋯−ckxk1 - c_1 x - c_2 x^2 - \cdots - c_k x^k
  3. 分子来自初值分子 $P(x)$ 的次数小于 $k$，由前 $k$ 个初值与系数共同确定。
    P(x)=∑i=0k−1(ai−∑j=1icjai−j)xiP(x) = \sum_{i=0}^{k-1}\left(a_i - \sum_{j=1}^{i} c_j a_{i-j}\right) x^i
  4. 展开取系数把 $F(x)$ 做部分分式分解并展开成幂级数，$x^n$ 前的系数正是 $a_n$。
    F(x)=∑iCi1−λix  ⇒  an=∑iCiλinF(x) = \sum_i \frac{C_i}{1 - \lambda_i x} \;\Rightarrow\; a_n = \sum_i C_i \lambda_i^n

优化与扩展

当递推阶数 $k$ 变大，货柜变长，矩阵乘法从“轻量操作”变成“重体力活”。工程师开始给传送带减负：第一招是让乘法只挑非零的位置下手；第二招是顺手把常数项也装进货柜。

伴随矩阵非常“稀疏”——每行最多只有两个非零元。常规矩阵乘法是 $O(k^3)$，针对稀疏结构可以压到 $O(k^2)$。另外，如果递推式里混入常数项 $d$（例如汉诺塔 $h_n = 2h_{n-1} + 1$），可以用“升维”技巧把 $d$ 伪装成状态的一部分。

减负之后的传送带又快又省。现在，把这台“时间穿梭机”开进动态规划车间，处理更多真实订单。

[anan−1⋮an−k+11]=[c1c2⋯ckd10⋯00⋮⋮⋱⋮⋮00⋯1000⋯01][an−1an−2⋮an−k1]\displaystyle \begin{bmatrix} a_n \\ a_{n-1} \\ \vdots \\ a_{n-k+1} \\ 1 \end{bmatrix} = \begin{bmatrix} c_1 & c_2 & \cdots & c_k & d \\ 1 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \\ 0 & 0 & \cdots & 0 & 1 \end{bmatrix} \begin{bmatrix} a_{n-1} \\ a_{n-2} \\ \vdots \\ a_{n-k} \\ 1 \end{bmatrix}
  1. 增广状态把常数 $1$ 塞进状态向量末尾，非齐次递推被改写成 $(k+1)$ 维的齐次线性递推。
    v⃗n=[anan−1⋯an−k+11]T\vec{v}_n = \begin{bmatrix} a_n & a_{n-1} & \cdots & a_{n-k+1} & 1 \end{bmatrix}^{\mathsf{T}}
  2. 末行自持矩阵最后一行是 $[0, \ldots, 0, 1]$，保证新增的常数位每次流转后仍是 1。
    last row=[0⋯01]\text{last row} = \begin{bmatrix} 0 & \cdots & 0 & 1 \end{bmatrix}
  3. 稀疏乘法伴随矩阵每行至多 2 个非零元，乘法只扫描非零项。
    C[i][j]=∑k: A[i][k]≠0A[i][k] B[k][j]C[i][j] = \sum_{k:\, A[i][k] \ne 0} A[i][k]\, B[k][j]
  4. 全程取模大数场景下每一步乘法后取模，防止中间结果指数级爆炸。
    (A×B)ij mod p=(∑kAikBkj) mod p(A \times B)_{ij} \bmod p = \left(\sum_k A_{ik} B_{kj}\right) \bmod p

动态规划应用

动态规划里有一大类问题，状态转移恰好长成“线性递推”的模样：今天的方案数 = 昨天的方案数 + 前天的方案数。这类 DP 表本来要一张一张填，如今可以直接用矩阵快速幂“跳着填”。

比如经典的爬楼梯问题：每次走 1 级或 2 级，到第 $i$ 级的方案数满足 $dp_i = dp_{i-1} + dp_{i-2}$。带权重的版本写成 $dp_i = w_1 dp_{i-1} + w_2 dp_{i-2}$，系数固定，正好是二阶常系数线性递推。

同一台传送带，换一张操作手册就能服务不同订单。理解底层引擎——递推、矩阵、快速幂——你就能在任何线性场景里自由“穿梭”。

[dpidpi−1]=[w1w210][dpi−1dpi−2]=[w1w210]i−1[dp1dp0]\displaystyle \begin{bmatrix} dp_i \\ dp_{i-1} \end{bmatrix} = \begin{bmatrix} w_1 & w_2 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} dp_{i-1} \\ dp_{i-2} \end{bmatrix} = \begin{bmatrix} w_1 & w_2 \\ 1 & 0 \end{bmatrix}^{i-1} \begin{bmatrix} dp_1 \\ dp_0 \end{bmatrix}
  1. 识别线性转移先确认 $dp_i$ 只由最近几个 $dp$ 值做常数线性组合，不依赖外部输入。
    dpi=w1dpi−1+w2dpi−2dp_i = w_1 dp_{i-1} + w_2 dp_{i-2}
  2. 状态向量化把相邻两个 $dp$ 值拼成向量，转移写成一阶矩阵形式。
    s⃗i=[dpidpi−1]T\vec{s}_i = \begin{bmatrix} dp_i & dp_{i-1} \end{bmatrix}^{\mathsf{T}}
  3. 快速幂直达从 $\vec{s}_i = M^{i-1} \vec{s}_1$ 出发，用矩阵幂一次性得到任意远处的状态。
    s⃗i=Mi−1s⃗1\vec{s}_i = M^{i-1} \vec{s}_1
  4. 识别边界若转移带取 $\max/\min$ 或依赖阶段变量，就不能直接矩阵化。
    dpi=max⁡(dpi−1,dpi−2)+1⇒不适用dp_i = \max(dp_{i-1}, dp_{i-2}) + 1 \quad \Rightarrow \quad \text{不适用}

AI 应用场景

场景1：算法竞赛中的超大 n 递推求解

阶段：核心算法设计与性能加速

解决的问题：逐项递推求斐波那契第 $10^9$ 项需要 $10^9$ 次循环，在竞赛时限内几乎不可能完成；把递推写成 2×2 矩阵并用快速幂，只需约 30 次矩阵乘法即得结果。数学建模与算法题中经常出现“n 巨大 + 取模”的组合。

具体案例：LeetCode “第 N 个泰波那契数”、Codeforces 递推类题目中，官方题解普遍给出“构造转移矩阵 + 二进制快速幂”的写法，配合取模在毫秒级输出答案。

场景2：时间序列线性递推预测

阶段：特征建模与快速推理

解决的问题：某些业务指标可近似为线性递推，如“本周库存 = 0.7×上周 + 0.2×上上周”。传统迭代预测要一步步推到目标期，长期预测成本高；矩阵快速幂把“预测 1000 周”压缩成约 10 次矩阵乘法，且天然适合批量并行。

具体案例：供应链系统对数千个 SKU 的周需求做 52 周滚动预测，每个 SKU 用各自的转移矩阵，批量快速幂后在秒级返回全部远期期望值，支撑库存与产能规划。

场景3：大规模线性动态规划加速

阶段：推理加速与模型服务优化

解决的问题：有限状态马尔可夫链、线性二次调节器等模型的分量更新满足线性递推；当步数 $n$ 极大时，逐轮 DP 更新成为瓶颈。把 DP 转移矩阵化并用快速幂，可将推理从 $O(n)$ 降到 $O(\log n)$，且矩阵乘天然可并行。

具体案例：机器人路径规划中“走恰好 $n$ 步到达目标的方案数”是典型的斐波那契型 DP，当 $n$ 高达 $10^{18}$ 时，循环不可能完成，矩阵快速幂在微秒级给出结果。

Python 演示

python51 行
MOD = 10 ** 9 + 7 def mat_mul(A, B):    n = len(A)    C = [[0] * n for _ in range(n)]    for i in range(n):        for k in range(n):            if A[i][k]:                aik = A[i][k]                for j in range(n):                    C[i][j] = (C[i][j] + aik * B[k][j]) % MOD    return C def mat_pow(M, p):    n = len(M)    R = [[1 if i == j else 0 for j in range(n)] for i in range(n)]    while p > 0:        if p & 1:            R = mat_mul(R, M)        M = mat_mul(M, M)        p >>= 1    return R def kth_term(coeffs, init, n):    k = len(coeffs)    if n < k:        return init[n] % MOD    M = [[0] * k for _ in range(k)]    for j in range(k):        M[0][j] = coeffs[j] % MOD    for i in range(1, k):        M[i][i - 1] = 1    Mn = mat_pow(M, n - k + 1)    ans = 0    for j in range(k):        ans = (ans + Mn[0][j] * (init[k - 1 - j] % MOD)) % MOD    return ans if __name__ == '__main__':    # 斐波那契数列 a_n = a_{n-1} + a_{n-2}    fib = ([1, 1], [0, 1])    print("Fibonacci:")    for n in range(10):        print("F(%d) = %d" % (n, kth_term(fib[0], fib[1], n)))    print("F(10**9) mod MOD =", kth_term(fib[0], fib[1], 10 ** 9))     # 三阶递推 a_n = a_{n-1} + a_{n-2} + a_{n-3}    tri = ([1, 1, 1], [0, 1, 1])    print("Tribonacci:")    for n in range(8):        print("T(%d) = %d" % (n, kth_term(tri[0], tri[1], n)))
目的：实现任意 $k$ 阶常系数线性递推的矩阵快速幂求解，输入系数、初值与目标项号 $n$，在 $O(k^3 \log n)$ 时间内返回第 $n$ 项（对 $10^9+7$ 取模）。
  1. def mat_mul(A, B):矩阵乘法，但在 A[i][k] 非零时才累加，利用稀疏性省时间。
  2. C[i][j] = (C[i][j] + aik * B[k][j]) % MOD每次累加后立刻取模，防止中间结果爆炸。
  3. R = [[1 if i == j else 0 for j in range(n)] for i in range(n)]单位矩阵作为幂运算初值，相当于乘法里的"1"。
  4. if p & 1: R = mat_mul(R, M)二进制位为 1 时把对应幂乘入结果，这是快速幂的核心分支。
  5. M = mat_mul(M, M)每轮把矩阵平方，对应 $M^{2^j} \to M^{2^{j+1}}$。
  6. M[0][j] = coeffs[j] % MOD在转移矩阵首行写入递推系数。
  7. M[i][i - 1] = 1在次对角线放 1，实现状态“顺位下传”。
  8. Mn = mat_pow(M, n - k + 1)用快速幂直接算出第 $n$ 步的转移矩阵。

常见误区

误区我一直以为矩阵快速幂是斐波那契的专属技巧，最多能处理二阶递推，一遇到三阶、五阶递推就傻眼了。

正解任意 $k$ 阶常系数线性递推都能构造 $k \times k$ 伴随矩阵并套用快速幂，复杂度 $O(k^3 \log n)$，只是矩阵变大。带常数项的非齐次递推（如汉诺塔 $h_n = 2h_{n-1} + 1$）升一维照样能处理，就像货柜多留一格放“常数 1”。

为何常见：教程和面试题几乎都用斐波那契当例子，二阶 2×2 矩阵最简洁，容易让人以偏概全。

误区特征方程和矩阵的特征值不都一样吗？既然递推对应矩阵，直接用 $\det(M - \lambda I)$ 算通项不就行了？

正解特征方程由递推式直接导出，是纯代数多项式 $x^k - c_1 x^{k-1} - \cdots - c_k = 0$；矩阵特征值是 $\det(M - \lambda I) = 0$ 的根。两者只在伴随矩阵这种特殊结构下恰好一致，一般矩阵求通项还要考虑能否对角化，不能混用公式。

为何常见：两个概念都叫“特征”，且伴随矩阵下结论恰好相同，初学者极易混淆。

误区我按矩阵快速幂写了代码，小 n 都对，一提交大 n 就出现负数或乱码，肯定是算法写错了。

正解递推值呈指数增长，比如斐波那契第 100 项约有 21 位数字。必须在矩阵乘法的每次累加后立即取模，而不是最后统一取一次。“先乘完再取模”会先撑爆整数范围。

为何常见：本地用小数据测试通过后，没有意识到 $n$ 到 $10^9$ 时中间结果会指数爆炸。

误区特征方程一旦有重根，通项公式里的 $\lambda^n$ 就重复了，初值解不出来，我觉得这方法失效了。

正解重根时通项要乘上 $n$ 的多项式因子：$r$ 重根对应 $(A_0 + A_1 n + \cdots + A_{r-1} n^{r-1}) \lambda^n$。因为重根情况下需要“广义特征向量”，线性无关的解不止 $\lambda^n$ 一个。

为何常见：线性代数里重特征值需要 Jordan 标准形的知识，非数学专业的同学很少接触。

误区快速幂不就是递归地调用 $M^n = M^{n-1} \times M$ 吗？本质还是循环 $n$ 次。

正解朴素递归并没有加速。真正把 $O(n)$ 降到 $O(\log n)$ 的关键是“指数二进制分解 + 迭代平方”：预处理 $M^{2^j}$，再按二进制位选择性累乘，总共约 $\log_2 n$ 次矩阵乘法。

为何常见：初学者先学递推式，又见过递归写法，容易把“递归 + 矩阵相乘”误当成“快速幂”。

面试题

Q1. 斐波那契数列满足 F(0)=0、F(1)=1，则 F(10) 等于多少？

单选题 · easy

  • A.34
  • B.55← 正确答案
  • C.89
  • D.144

答案：B。逐项递推可得 0,1,1,2,3,5,8,13,21,34,55，第 10 项是 55。34 是 F(9)，89 是 F(11)，144 是 F(12)。就像传送带上的第 10 站货量是 55，34 还差一站，89 已经跑过头。

Q2. 用矩阵快速幂求斐波那契第 n 项的时间复杂度是？

单选题 · easy

  • A.O(n)
  • B.O(log n)← 正确答案
  • C.O(n log n)
  • D.O(1)

答案：B。快速幂把 n 次矩阵乘法压缩成约 log₂n 次，所以是 O(log n)。O(n) 是朴素递推，O(1) 对一般 n 不现实，O(n log n) 常见于每步重算的笨办法。这就是“时间穿梭引擎”的价值：跑 log 圈而非 n 圈。

Q3. 对于 k 阶常系数线性递推，构造的转移矩阵大小是？

单选题 · mid

  • A.k × 1
  • B.1 × k
  • C.k × k← 正确答案
  • D.2 × 2

答案：C。状态向量包含最近 k 个值、维度为 k，要将 k 维向量映射回 k 维向量，转移矩阵必须是 k×k。就像货柜有 k 格，操作手册必须能同时更新这 k 格。

Q4. 递推 a_n = 3a_{n-1} - 2a_{n-2} 对应的特征方程是？

单选题 · mid

  • A.x² - 3x + 2 = 0← 正确答案
  • B.x² + 3x - 2 = 0
  • C.x² = 3x + 2
  • D.x² - 2x + 3 = 0

答案：A。设 a_n = λⁿ 代入，得 λⁿ = 3λⁿ⁻¹ - 2λⁿ⁻²，两边除以 λⁿ⁻² 得 λ² = 3λ - 2，整理为 x² - 3x + 2 = 0。特征方程的系数搬运规则是“系数原样移项变号”，其他选项符号或位置错位。

Q5. 下列哪些数列可以通过常系数线性递推 + 矩阵快速幂高效求解？

多选题 · mid

  • A.斐波那契数列 F_n = F_{n-1} + F_{n-2}← 正确答案
  • B.卢卡斯数列 L_n = L_{n-1} + L_{n-2}← 正确答案
  • C.等比数列 G_n = 2G_{n-1}← 正确答案
  • D.质数数列 P_n = 第 n 个质数

答案：ABC。A、B 是二阶线性递推，C 是一阶常系数递推（矩阵退化为 1×1），三者都能构造常数转移矩阵。质数数列没有固定线性规则，无法写出行之有效的“操作手册”，D 不能套用。

Q6. 特征方程 x² - 2x + 1 = 0 对应的二阶递推通项形式是？

单选题 · extreme

  • A.A·1ⁿ + B·(-1)ⁿ
  • B.(A + Bn)·1ⁿ← 正确答案
  • C.A·1ⁿ + B·n·(-1)ⁿ
  • D.A·2ⁿ + B·1ⁿ

答案：B。x² - 2x + 1 = (x-1)²，特征根 λ=1 是二重根。重根时两个线性无关解是 1ⁿ 和 n·1ⁿ，通项为 (A + Bn)·1ⁿ = A + Bn。这就像两条节拍完全相同的传送带，必须给其中一条贴上“序号牌” n 才能区分它们。

Q7. 矩阵乘法能够进行的前提条件是？

单选题 · easy

  • A.两个矩阵尺寸完全相同
  • B.左矩阵的列数等于右矩阵的行数← 正确答案
  • C.两个矩阵都必须是方阵
  • D.左矩阵必须可逆

答案：B。矩阵乘法的定义要求内维匹配：左矩阵列数 = 右矩阵行数。同尺寸方阵只是特例，不可逆也照样能相乘。就像货柜的格数必须与手册的“行数”对齐，才能一格格运算。

Q8. 关于快速幂的二进制分解，下列说法正确的是？

多选题 · hard

  • A.指数 n 被拆成 2 的幂之和← 正确答案
  • B.M^(2^j) 由 M^(2^(j-1)) 平方递推而来← 正确答案
  • C.只有二进制位为 1 的位置参与累乘← 正确答案
  • D.必须用递归实现，否则会超时

答案：ABC。A、B、C 是快速幂三要素：拆分指数、迭代平方、按位选择性累乘。D 错误，迭代（while 循环）同样能实现且更常见，递归与性能无关。想象把 13 圈拆成 8+4+1，预制好 2 的幂，只在需要时取用。

Q9. 关于生成函数法，下列哪些说法正确？

多选题 · mid

  • A.F(x) = Σ a_n·xⁿ 把整个数列编码进一个幂级数← 正确答案
  • B.分母 1 - c₁x - …… - c_k x^k 来自递推系数← 正确答案
  • C.分子多项式由初值确定← 正确答案
  • D.F(x) 必须用傅里叶变换才能展开

答案：ABC。装袋、骨架（分母）、初值（分子）是生成函数三步曲，A、B、C 全部正确。D 错误：展开靠部分分式分解与几何级数技巧，与傅里叶变换无关。

Q10. 一个动态规划问题能用矩阵快速幂优化的前提是？

单选题 · hard

  • A.状态转移是线性且系数恒定← 正确答案
  • B.n 越大越适合
  • C.必须包含至少三维状态
  • D.只适用于斐波那契类问题

答案：A。矩阵快速幂要求状态转移是常系数线性齐次的，换成 max/min 或阶段依赖系数就会失效。n 大只是“收益更大”，不是前提；状态维数由问题决定；方法适用于所有线性递推 DP，远不止斐波那契。