本文大概是关于构造递推序列的矩阵

绪言

算法竞赛中经常会遇到快速求一类 $k$ 阶递推序列的第 $n$ 项的题目, 可以通过 $O(k^3 \log_2 n)$ 的时间复杂度的 矩阵快速幂 来解决, 即通过构造出矩阵并对矩阵快速幂来快速解决

比如对于斐波那契数列 $f_0 = f_1 = 1, f _ i = f _ {i - 1} + f _ {i - 2}, i\geq 2$ , 可以通过构造下面的矩阵来解决

$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} f _ {i} \\ f _ {i - 1} \end{bmatrix} = \begin{bmatrix} f _ {i + 1} \\ f _ {i} \end{bmatrix}$

所以说对于求第 $n$ 项就变成了

$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} ^ {n - 1} \begin{bmatrix} f _ {1} \\ f _ {0} \end{bmatrix} = \begin{bmatrix} f _ {n} \\ f _ {n - 1} \end{bmatrix}$

然后矩阵可以通过快速幂求, 答案就取最后向量的第一维就好了. 但是为什么矩阵内的数字是这个以及是如何构造出来的, 就要了解矩阵构造相关知识了

准备工作

首先递推式要求是线性且已知的, 这也是进行构造的基础

本文中, 将需要进行矩阵快速幂的矩阵暂时叫做构造矩阵. 由于矩阵乘法的性质, 对于 $k$ 阶线性递推式的构造矩阵的大小为 $k\times k$

矩阵构造

由特殊向一般, 由具体向抽象, 考虑较为简单的二阶递推式的构造矩阵(可以尝试自己推导一阶递推式), 也就是 $f _ i = \alpha f _ {i - 1} + \beta f _ {i - 2}$ , 先写出形式:

$\begin{bmatrix} ? & ? \\ ? & ? \end{bmatrix} \begin{bmatrix} f _ {i} \\ f _ {i - 1} \end{bmatrix} = \begin{bmatrix} f _ {i + 1} \\ f _ {i} \end{bmatrix}$

也就是

$\begin{bmatrix} ? & ? \\ ? & ? \end{bmatrix} \begin{bmatrix} f _ {i} \\ f _ {i - 1} \end{bmatrix} = \begin{bmatrix} f _ {i + 1} \\ f _ {i} \end{bmatrix} = \begin{bmatrix} \alpha f _ {i} + \beta f _ {i - 1} \\ f _ {i} \end{bmatrix}$

所以可以得到第一列为 $\begin{bmatrix} \alpha , \beta \end{bmatrix}$ , 从而可以简单地推出来:

$\begin{bmatrix} \alpha & \beta \\ 1 & 0 \end{bmatrix} \begin{bmatrix} f _ {i} \\ f _ {i - 1} \end{bmatrix} = \begin{bmatrix} f _ {i + 1} \\ f _ {i} \end{bmatrix} = \begin{bmatrix} \alpha f _ {i} + \beta f _ {i - 1} \\ f _ {i} \end{bmatrix}$

至此, 就豁然明朗了

相信你对于简单的普通递推式了如指掌了, 接下来可以尝试自己推一下 $k$ 阶的证明, 可以参照上面的步骤进行简单的类比.

接下来考虑一个复合的递推式:

序列 $\{f_i\}$ 为斐波那契数列(形式在上文中已给出), 序列 $F _ i = F _ {i - 1} + F _ {i - 2} + f _ i$ , 求 $F$ 的构造矩阵