线性递推的求解
线性递推的求解
参考文献：2019集训队论文，钟子谦《两类递推数列的性质和应用》
这篇文章介绍如何求解，线性递推的应用更多在这里
数列$\{a_0,a_1,\cdots \}$
向量序列$\{v_0,v_1,\cdots\}$
矩阵序列$\{M_0,M_1,\cdots\}$
的线性递推
序列$a_0,a_1,\cdots,a_n$的线性递推的定义应当是
对于一个常数列$r_0,r_1,\cdots,r_m(r_0=1)$
为了便于表示，令
$\lambda(i,r)=\sum_{j=1}^{m}a_{i-j}r_j$
$\Delta(i,r)=\sum_{j=0}^m a_{i-j}$
满足$\forall i\ge m,\Delta(i,r)=0$
这似乎与与平常的认知有一些冲突
求解序列的最短线性递推: Berlekamp-Massey 算法
对于一个$n$个元素的数列$a_{1,\cdots, n}$，求出它的最短线性递推式
为了便于理解约定下文求出的是最小的$m$和对应的$r_1,\cdots r_m$使得$\forall i\in [m+1,n],a_i=\sum_{j=1}^{m}a_{i-j}r_j$
很显然使用高斯消元可以在$O(n^3)$的时间内求解
而$\text{Berlekamp-Massey(BM)}$算法是通过依次对于前$i$项构造，
添加每一项时在$O(n)$的时间内找到一个可行的构造方法，将复杂度降低到了$O(n^2)$
算法过程
为了更好描述，设$r$的阶为$d(r)$
考虑依次加入每个数$a_i$，设当前$d(r)=m$，上一次的递推是$p$,$p$出现不匹配的位置是$f$
特别的，初始状态的递推是$r=\{ \},f=0$
$1.\Delta(i,r)=0$，那么不需要扩展
2.$\Delta(i,r)\ne 0$
$\text{i}.m=0$，此时只有一种情况即插入了第一个$a_i\ne 0$，唯一的递推序列就是$d(r’)=i,r_j=0(j>0)$，此时显然成立
$\text{ii}.m\ne 0$
构造思路是找到一个$r’$使得$\forall j\in[d(r’),i-1],\lambda(j,r’)=0\and \lambda (n,r’)=\Delta(i-1,r)$
那么当前合法的转移就是$r+r’$
设$t=\frac{\Delta(n,r)} {\Delta(f,p)}$
构造$r’=t \cdot x^{i-f-1}(1-p)$
写出来就是
$r’=\{\underbrace{0,\cdots,0},t\cdot (1-p)\}$
$ \ \ \ \ \ \ \ \ i-f-1$个$0$
$r’=\{\underbrace{0,\cdots,0},t,-t\cdot p_{1},-t\cdot p_{2}\cdots,-t\cdot p_{d(p)} \}$
$ \ \ \ \ \ \ \ \ i-f-1$个$0$
此时，$d(r’)=i-f+d(p)$
当$j\in [d(r’)+1,i-1]$时，$\lambda(j,r’)=\sum_{k=i-f}^{d(r’)}a_{j-k}r’_k$
$=t\cdot( a_{j-(i-f)}-\lambda(j-(i-f),p))$
由于$p$对于$j\in[d(r’)+1-(i-f),i-1-(i-f)]=[d(p)+1,f-1]$，$p$这个递推式成立
即$\lambda(j,r’)=0$
当$j=i$时，
$\lambda(i,r’)=t\cdot (a_{i-(i-f)}+\lambda(i-(i-f),p))=t\cdot \Delta(f,p)$
即$\lambda (i,r’)=\Delta(n,r)$
完成了我们想要的构造，所以每次记录上一次的失配位置，即可找到最小递推式
关于为什么求得的就是最小递推，可以看论文里的证明
求解向量序列的线性递推
对于长度为$n$的向量序列$\{v_0,v_1,\cdots\}$
在模$P$意义下，随机一个向量$u$，构造标量序列$\{v_0u,v_1u,\cdots\}$
构造和求解这个标量序列的线性递推，复杂度均为$O(n^2)$
求得的线性递推也为向量序列的线性递推的概率为$1-\frac{n} {P}$，通常认为不会错
(可以认为复杂度与读入同阶?)
求解矩阵序列的线性递推
对于长度为$n$的矩阵序列$\{M_0,M_1,\cdots\}$
同样在模$P$意义下，随机两个向量$u,v$，构造标量序列$\{uM_0v,uM_1v,\cdots\}$
求解线性递推的复杂度为$O(n^2)$
但是构造标量序列需要计算$n$次向量与矩阵的乘法，复杂度为$O(n^3)$
(可以认为复杂度与读入同阶?)