Berlekamp-Massey 算法(最短线性递推)

参考文献：2019集训队论文，钟子谦《两类递推数列的性质和应用》给出了详细阐述

算法简介

对于一个$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)$

$\lambda(n,r)=\sum_{i=1}^{d(r)}a_{n-i}r_i$

$\Delta(n,r)=a_n-\lambda (n,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$，此时显然成立

$\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)$

完成了我们想要的构造，所以每次记录上一次的失配位置，即可找到最小递推式

然后，上面的构造方法只满足构造出一个合法的线性递推式，并没有证明是$m$是最小的

但是在OI竞赛中，通常我们只是需要快速求出递推式，并不要求最短线性递推

如果想要看到严谨的证明还请移步2019集训队论文