算法引入
Berlekamp-Massey算法可以在$O(n^2)$的时间内求出长度为$n$的已知数列的最短递推式，再配合常系数齐次线性递推就可以快速求出数列的任意项。
现在给你一个数列，考虑如何构造出其最短递推式。
算法流程
对于一个$n$项的数列 $A=\{a_1,a_2,…,a_n\}$ 和另一个$m$项的数列 $R=\{r_1,r_2,…,r_m\}(m\le n)$ ，当$\forall k>m$，都满足$a_k=\sum\limits_{i=1}^mr_ia_{k-i}$时，我们称$R是$A的一个递推式，对于所有满足条件的$R$，我们将$m$最小的$R$称为$A$的最短线性递推式。
现在我们考虑用增量构造法构造一个$N$项的数列$A$的最短线性递推式$R$
假设我们当前处理到位置$n$，$\{a_1,a_2,…,a_{n-1}\}$的最短线性递推式为$\{r_1,r_2,…,r_m\}$，记第$i$次更改最短线性递推式为$R_i$，特别的，$R_0=\{\emptyset\},R_{cur}=\{r_1,r_2,…,r_m\}$即为当前最短线性递推式。
设$\Delta n=a_n-\sum\limits_{i=1}^mr_ia_{n-i}$，现在按$\Delta n$的取值分两种情况考虑
- $\Delta n=0$，则$R_{cur}$为$\{a_1,a_2,…,a_n\}$的最短线性递推式
- $\Delta n\not=0$，则$R_{cur}$在位置$n$出错，我们要构造出$R_{cur+1}$来修正这个递推式。
修正递推式时又要分两种情况
- $cur=0$，我们直接构造一个递推式 $R_1=\{r_1,r_2,r_3,…,r_n\}$，其中 $r_1=r_2=\cdot\cdot\cdot=r_n=0$
- $cur\not=0$，考虑构造一个增量构造式$R_{\Delta}$满足$R_{cur+1}=R_{cur}+R_{\Delta}$，接下来我们将对如何构造$R_{\Delta}$展开讨论。
定义$fail_{i}$表示递推式$R_{i}$出错的最早位置，那么此时按照定义$fail_{cur}=n$。
假设$R_{\Delta}$一共有$m’$项，考虑$R_{\Delta}$要满足的条件：
- $\Delta n=\sum\limits_{i=1}^{m’}R_{\Delta,i}a_{n-i}$
- $\forall m’<k<n,0=\sum\limits_{i=1}^{m’}R_{\Delta,i}a_{k-i}$
考虑到$R_{best}$这个递推式满足类似的条件，其中 $best$ 是满足 $fail_{best}-len_{best}$ 最小的一项：
- $\Delta fail_{best}=a_{fail_{best}}-\sum\limits_{i=1}^{m_{best}}R_{best,i}a_{fail_{best}-i}$
- $\forall m_{best}<k<fail_{best},0=a_k-\sum\limits_{i=1}^{m_{best}}R_{best,i}a_{k-i}$
我们设$t=\frac{\Delta n}{\Delta fail_{best}},b=\{t,-t\times r_{best,1},-t\times r_{best,2},…,-t\times r_{best,m_{best}}\}$
这启示我们按照如下方式构造$R_{\Delta}$：
- $\forall fail_{best}<k<n$，我们给$a_{n-k}$分配$0$作为系数
- $\forall fail_{best}-m_{best}\le k\le fail_{best}$,我们给$a_{n-k}$分配$b_{fail_{best}-k+1}$作为系数。
这样构造出来的数列
满足条件
再让$R_{cur+1}=R_{cur}+R_{\Delta}$即可。
由于最坏情况下可能会修改$O(n)$次，所以复杂度$O(n^2)$