两类递推数列

此博客是抄论文的，你可以认为是转载的

1.线性递推数列

有限数列显然是线性递推数列。
无限数列$a_i$ai​设其生成函数为$A(x)$A(x)
那么如果$A(x)$A(x)能被表示为$\frac {C(x)}{B(x)}$B(x)C(x)​的形式，其中$B(x)[x^0] = 1$B(x)[x0]=1，则$A(x)$A(x)是线性递推数列。
常数项为$1$1是因为递推式你要让$\sum_{j=0}b_ja_{i-j} = 0$∑j=0​bj​ai−j​=0来递推出$a_i$ai​所以常数项需要为$1$1。
能这样表示是因为线性递推实质上就是$A(x)B(x) = C(x)$A(x)B(x)=C(x)，其中$B(x)$B(x)是我们的线性递推式。

对于一个线性递推数列$a_i$ai​，假设他前$i$i项的最短递推式是$R^{(i)}$R(i)，长度为$l_i$li​，那么如果$R^{(i-1)}$R(i−1)不是前$i$i项的最短递推式，那么有$l_i \geq \max(l_{i-1},i+1-l_{i-1})$li​≥max(li−1​,i+1−li−1​)，且这个等号是可以通过构造取到的。
首先$l_i \geq l_{i-1}$li​≥li−1​显然，如果$l_i \leq i-l_{i-1}$li​≤i−li−1​的话：

实在不知道怎么用语言表示交换和号。
也就是说如果$l_i \leq i-l_{i-1}$li​≤i−li−1​那么原来的递推式必可以继续用。

接下来我们给出在$R^{(i-1)}$R(i−1)不是前$i$i项的递推式时$l_i = \max(l_{i-1},i+1-l_{i-1})$li​=max(li−1​,i+1−li−1​)的构造方案，也就是$BM$BM算法。

也就是说每次增长递推式，我们都可以用这个方法使得增长时$l_i = i+1-l_{i-1}$li​=i+1−li−1​，不增长时$l_i = l_{i-1}$li​=li−1​。
因为上文证明了$l_i \geq \max(l_{i-1},i+1-l_{i-1})$li​≥max(li−1​,i+1−li−1​)，所以这个算法对于有限长度的数列求出的递推式一定是最短的。

对于无限长的数列，

所以我们只需要取最短递推式长度的两倍即可。
边界情况：第一次增长递推式的时候，$a_i$ai​应该是第一个非$0$0元素，那么$l_i = i$li​=i个$0$0即为前$i$i个数的最短递推式，也就是根本没有递推，同时也满足$l_i \geq i+1-l_{i-1},(l_{i-1}=0)$li​≥i+1−li−1​,(li−1​=0)。

线性递推求第$n$n项：

向量序列的最短递推式：

矩阵的零化多项式：使得矩阵$M$M：
$f(M) = \sum_{i=0}^n a_iM^i = 0$f(M)=∑i=0n​ai​Mi=0
矩阵的最小多项式：
零化多项式中次数最低的多项式。
如何求矩阵的最小多项式：
直接求${I,M,M^2...}$I,M,M2...的最短递推式即可，对于稀疏矩阵可以做到$O(n(n+e))$O(n(n+e))。

2.整式递推数列