「递推式」关于一类递推序列的矩阵构造

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

绪言

算法竞赛中经常会遇到快速求一类 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 的构造矩阵

这个还是仿照上面的证明, 这里由于公式写起来 \LaTeX 代码会极其复杂, 于是手写推导过程了qwqwq

推导过程.png

(图片link: https://i.loli.net/2019/10/01/OoZTQBa6HieuAd4.png)

这样, 就可以解决部分复合递推式构造矩阵了. 现在仔细考虑上面的推导过程使用到了什么特别的东西. 注意到这个其实就是将两个斐波那契数列合在一起并修改第一行的递推和.

部分常用技巧

求数列和

继续上面的问题, 也就是求 f _ i = \alpha f _ {i - 1} + \beta f _ {i - 2} 的递推矩阵, 已经比较简单了. 现在考虑对于 f 求一个前缀和 F _ i = \sum _ {i = 0} f_i , 再求递推矩阵求解 F

推导过程.png

(图片link: https://i.loli.net/2019/10/01/QyXvtLlqmdNURYg.png)

其实就是将第一列复制一份到最后一列, 并补成方阵的形式, 最后令右下角的值为 1 即可

恒等变换

比如 e ^ {\ln x} = x

对于 f _ i = f _ {i - 1} \times f _ {i - 2} 之类的式子, 可以考虑两边同时取 \ln 就变成了:

\ln f _ i = \ln f _ {i - 1} + \ln f _ {i - 2}

坚持原创技术分享,您的支持将鼓励我继续创作!