常系数齐次线性递推

题目链接

题目描述

数列$\{a_n\}$满足$k$阶线性递推关系：$a_n={\sum }_{i=1}^k{f}_i{a}_{n-i}(n\ge k)$。

现给定$n,k$以及$f_1,f_2,...,f_k,a_0,a_1,...,a_{k-1}$，求$a_n\mathrm{m}\mathrm{o}\mathrm{d}998244353$的值。

数据范围

$n\le 10^9,k\le 32000$

思路

令$F=\left[\begin{array}{cccc}0& 1& ...& 0\\ 0& 0& \ddots & 0\\ 0& 0& ...& 1\\ f_k& f_{k-1}& ...& f_1\end{array}\right]$。
则$\left[\begin{array}{c}{a}_n\\ a_{n+1}\\ ...\\ a_{n+k-1}\end{array}\right]=F^n\left[\begin{array}{c}{a}_0\\ a_1\\ ...\\ a_{k-1}\end{array}\right]$。
$F$的特征多项式为$g(\lambda )=|\lambda I-F|={\lambda }^k-{\sum }_{i=1}^k{f}_i{\lambda }^{k-i}$。
根据代数基本定理，可以把$g(\lambda )$表示为$g(\lambda )={\prod }_{i=1}^t(\lambda -{\lambda }_i{)}^{m_i}$，其中${\lambda }_i$各不相同，且${\sum }_{i=1}^t{m}_i=k$。
因此$a_n={\sum }_{i=1}^t{\lambda }_i^n({\sum }_{j=1}^{m_i}{c}_{ij}{n}^{j-1})$，其中$c_{ij}$可以通过待定系数法确定。
但是${\lambda }_i$咋解？$c_{ij}$咋求？好像有点麻烦。

这时，还需要用到Hamilton-Cayley定理——$g(F)=F^k-{\sum }_{i=1}^k{f}_i{F}^{k-i}=O$。

若$r(\lambda )={\lambda }^n\mathrm{m}\mathrm{o}\mathrm{d}g(\lambda )={\sum }_{i=0}^{k-1}{r}_i{\lambda }^i$，
则$\left[\begin{array}{c}{a}_n\\ a_{n+1}\\ ...\\ a_{n+k-1}\end{array}\right]=r(F)\left[\begin{array}{c}{a}_0\\ a_1\\ ...\\ a_{k-1}\end{array}\right]$，
则$a_n={\sum }_{i=0}^{k-1}{r}_i{a}_i$。

总结一下：

1. 求出递推关系的特征多项式$g(\lambda )={\lambda }^k-{\sum }_{i=1}^k{f}_i{\lambda }^{k-i}$。
2. 求出$r(\lambda )={\lambda }^n\mathrm{m}\mathrm{o}\mathrm{d}g(\lambda )={\sum }_{i=0}^{k-1}{r}_i{\lambda }^i$。这一步需要多项式快速幂+取模。
3. 求出$a_n={\sum }_{i=0}^{k-1}{r}_i{a}_i$。