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

\[\forall i\in[len+1,p-1],\sum_{j=1}^{len} D_j A_{i-j}=A_i \]

\[\sum D_j A_{n-j} = A'_n \]

所以，我们是不是可以利用某一个之前失配的\(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\n",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;
} 

测试可以到 https://www.luogu.com.cn/problem/U160944