线性递推的求解（Berlekamp-Massey）
线性递推的求解（Berlekamp-Massey）
参考文献：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\) 的序列为一个线性递推序列。
稍作变换可以得到更加符合常理的形式：\(a_i=\sum_{j=1}^m r'_j \cdot a_{i-j}\)。
求解序列的最短线性递推: 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\)。
\(\Delta(i,r)=0\)，那么不需要扩展。
\(\Delta(i,r)\ne 0\)，
\(m=0\)，此时只有一种情况即插入了第一个 \(a_i\ne 0\)，唯一的递推序列就是 \(d(r')=i,r_j=0(j>0)\)，此时显然成立
\(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)\)。
（可以认为复杂度与读入同阶?）