「NOTE」常系数齐次线性递推

要不是考到了，我还没发现这玩意我不是很会……

# 前置

多项式取模；
矩阵快速幂。

# 常系数齐次线性递推

描述的是这么一个问题，给定数列 $c_1,c_2,\dots,c_k$ 以及数列 $f$ 的前 $k$ 项 $f_0,f_1,\dots,f_{k-1}$，已知 $f$ 有如下递推公式：

$\begin{aligned} (n\ge m)&&f_{n}=\sum_{i=1}^kc_if_{n-i} \end{aligned}$

求 $f_n \bmod 998244353$，其中 $n$ 可以很大，$k$ 是 $10^5$ 左右的数。

常系数：递推式的系数 $c_i$ 均为常数；
齐次：这意味着递推式没有常数项（如果有常数项就别想了）；
线性：$f_i$ 的指数都为 $1$。

# 算法原理

对于这种系数为常数的问题，我们有一个通用的解法 —— 矩阵快速幂：

$\begin{bmatrix}f_{n}\\f_{n + 1}\\\vdots\\f_{n + k - 1}\end{bmatrix}=\begin{bmatrix}0&1&0&\cdots&0\\0&0&1&\cdots&0\\0&0&0&\cdots&0\\\vdots&\vdots&\vdots&\ddots&\vdots\\c_k&c_{k - 1}&c_{k - 2}&\cdots&c_1\end{bmatrix}\times\begin{bmatrix}f_{n - 1}\\f_{n}\\\vdots\\f_{n + k - 2}\end{bmatrix}$

记最后那个 $k\times k$ 的转移方阵为 $A$，初始列向量为 $St$。常规的计算方法即计算

$A^n\times St$

复杂度 $\mathcal O(k^3\log n)$，主要的瓶颈在于矩阵乘法。

下面要介绍的算法给出了这样一种构造，其中 $\{c_i\}$ 是针对 $A^n$（注意不仅与 $A$ 有关，还与指数 $n$ 有关）构造的数列 ——

$\begin{aligned} &A^n=\sum_{i=0}^{k-1}c_iA^i\\ &A^n\times St=\sum_{i=0}^{k-1}c_iA^i\times St \end{aligned}$

目前看来好像没有什么茄子用，仍然需要计算矩乘。但是我们真的需要 $A^n\times St$ 这整个向量吗？实际上我们只需要 $f_n$，即 $A^n\times St$ 的第一项。

再看看这个式子就可以发现它的用处了：

$(A^n\times St)_1=\sum_{i=0}^{k-1}(c_iA^i\times St)_1=\sum_{i=0}^{k-1}c_i(A^i\times St)_1$

$A^i\times St$ 的实际意义是将 $St$ 转移 $i$ 次。所以 $(A^i\times St)_1=f_i$，也即

$f_n=\sum_{i=0}^{k-1}c_if_i$

这样就免去了矩乘。

~~这就是这个算法的全部内容了？~~还剩下一个问题，$\{c_i\}$ 怎么构造？

定义函数 $C(x)$ 如下，则要求 $C(A)=A^n$。

$C(x)=\sum_{i=0}^{k - 1}c_ix^i$

接下来是一些魔法……如果我们有函数 $F(x)$ 满足

$F(A)=\sum_{i=0}^{k}f_iA^i=0$

且有 $G(x)$ 满足：

$x^n=G(x)F(x)+C(x)\to C(x)=x^n\bmod F(x)$

易得

$A^n=G(A)F(A)+C(A)=C(A)$

利用多项式取模对快速幂稍加改造就可以计算 $C(x)$。

「稍加改造」

说起来倒也简单，把多项式 $x$ 拿来做快速幂，对 $F(x)$ 取模。

然后我们发现又需要构造 $F(x)$……如果要对一个一般的方阵求 $F(A)=0$ 那确实很难，但常系数齐次线性递推的转移矩阵 $A$ 因为它的结构特殊，有一个简洁的构造：

$f_k=1$；
$f_{i}=c_{k-i}$（$0\le i\lt k$）。

至于为什么这样构造，就涉及到矩阵的特征向量的内容，和这个算法本身没有太紧的关联。有兴趣的读者可以参考 shadowice1984 的洛谷博客。

THE END

Thanks for reading!

我也曾隐约想过从这世界逃离
因为有无数次和最优解失之交臂
那时耀眼的自己定不会轻易容许
骄傲变得同墙角霉菌不差毫厘

——《我也曾想过一了百了(中文填词)》 By 洛天依

> Link 我也曾想过一了百了 - Bilibili