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

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

# 前置

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

# 常系数齐次线性递推

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

求 (f_n mod 998244353)，其中 (n) 可以很大，(k) 是 (10^5) 左右的数。

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

# 算法原理

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

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

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

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

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

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

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

这样就免去了矩乘。

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

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

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

且有 (G(x)) 满足：

易得

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

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

• (f_k=1)；
• (f_{i}=-c_{k-i})（(0le ilt k)）。

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

THE END

Thanks for reading!