线性递推的求解
参考文献：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 ige m,Delta(i,r)=0)
这似乎与与平常的认知有一些冲突
求解序列的最短线性递推: Berlekamp-Massey 算法
对于一个(n)个元素的数列(a_{1,cdots, n})，求出它的最短线性递推式
为了便于理解约定下文求出的是最小的(m)和对应的(r_1,cdots r_m)使得(forall iin [m+1,n],a_i=sum_{j=1}^{m}a_{i-j}r_j)
很显然使用高斯消元可以在(O(n^3))的时间内求解
而( ext{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) e 0)
( ext{i}.m=0)，此时只有一种情况即插入了第一个(a_i e 0)，唯一的递推序列就是(d(r')=i,r_j=0(j>0))，此时显然成立
( ext{ii}.m e 0)
构造思路是找到一个(r')使得(forall jin[d(r'),i-1],lambda(j,r')=0and 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},tcdot (1-p)})
$ i-f-1$个(0)
(r'={underbrace{0,cdots,0},t,-tcdot p_{1},-tcdot p_{2}cdots,-tcdot p_{d(p)}})
$ i-f-1$个(0)
此时，(d(r')=i-f+d(p))
当(jin [d(r')+1,i-1])时，(lambda(j,r')=sum_{k=i-f}^{d(r')}a_{j-k}r'_k)
(=tcdot( a_{j-(i-f)}-lambda(j-(i-f),p)))
由于(p)对于(jin[d(r')+1-(i-f),i-1-(i-f)]=[d(p)+1,f-1])，(p)这个递推式成立
即(lambda(j,r')=0)
当(j=i)时，
(lambda(i,r')=tcdot (a_{i-(i-f)}+lambda(i-(i-f),p))=tcdot 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))
(可以认为复杂度与读入同阶?)