Berlekamp_Massey算法是用来在(O(n^2))时间内求解长度为(n)的数列的最短递推式算法。
如果我们已经知道前(i)项的递推式(R,)它不满足第(n)项，我们如何来调整它使得它满足第(n)项？
考虑往(R)上面加上一个递推式(F.)
设(Delta_{i})表示第(i)个递推式在匹配失败位置上的(A_p-A'_p.A'_p)是用该递推式推出的第(p)项。
那么(F)应该满足：
对于(len_R<i<n,sum_{j=1}^{len_R} A_j F_{i-j}=A_i).
对于(i=n,sum_{j=1}^{len_R}A_j F_{n-j}=A_n-A'_n)
若满足这个式子，则(A-F)则会被修正成功。
观察一下这个式子，和之前匹配失败的递推式是很像的：设该递推式(D)失配于(p,)
所以，我们是不是可以利用某一个之前失配的(D)来构造出(F?)设(D)的失配差为(Delta_D.)
考虑将失配的(D)写成(A_p-sum D_j A_{p-j})的形式，则等式右边就是(Delta_D.)
那么可以将该式子两边同时除掉(Delta_D)使得等式右边是1，这样令该式子乘以(Delta_R)再用(R)减去就完成了修正。
系统地，设选择的失配递推式失配在位置(p,)当前递推式失配于(i,tmp=-frac{Delta_R}{Delta_D})则(F)构造：
1.F.resize(i-p-1)即 往里面塞这么多(0).可以理解为将递推式平移。
2.将(D)前面补一个(-1)并令它整体乘以(-tmp,)即如上面所说将(Delta_D)除成(1)再乘上(Delta_R).之所以是负的是因为后面将减法修正改成了加法，这里差一个负号。
3.R+=F即完成修正。
至于什么时候是最短的：似乎求距离最近的那个失配的递推式即可。（我也不会证 反正过了模板）
#include<bits/stdc++.h>
using namespace std;
typedef double ld;
vector<ld>ls,cur;
int n,lf,tot;
ld a[100010],ldt;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%lf",&a[i]);
for(int i=1;i<=n;++i){
ld dt=-a[i];
for(int j=0;j<cur.size();++j)
dt+=(a[i-j-1]*cur[j]);
if(fabs(dt)<=1e-7)continue;
if(!cur.size()){
cur.resize(i);
lf=i;
ldt=dt;
continue;
}
vector<ld>c(i-lf-1);
ld k=-dt/ldt;
c.push_back(-k);
for(int j=0;j<ls.size();++j)c.push_back(k*ls[j]);
if(c.size()<cur.size()) c.resize(cur.size());
for(int j=0;j<cur.size();++j)c[j]+=cur[j];
ls=cur,ldt=dt;lf=i;
cur=c;
}
while(cur.back()<=1e-7)cur.pop_back();
printf("%d
",cur.size());
for(int i=0;i<cur.size();++i){
if(fabs(cur[i])<=1e-7)cur[i]=0;
cout<<(double)cur[i]<<" ";
}
puts("");
return 0;
}