Berlekamp-Massey算法简单介绍

输入线性递推式的前几项，求解线性递推公式的系数。
例如斐波那契数列，输入前五项：
5
1 1 2 3 5
得到的结果为
2
1 1
第n项代表与前两项有关，(n-1)项的系数为1，(n-2)项的系数也为1

若输入的式子是$f(n)=f(n-1)+f(n-2)$则输出为
2
1 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof (x))
#define For(i,a,b) for (int i=a;i<=b;i++)
#define Fod(i,b,a) for (int i=b;i>=a;i--)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
#define _SEED_ ('C'+'L'+'Y'+'A'+'K'+'I'+'O'+'I')
#define outval(x) printf(#x" = %d\n",x)
#define outvec(x) printf("vec "#x" = ");for (auto _v : x)printf("%d ",_v);puts("")
#define outtag(x) puts("----------"#x"----------")
#define outarr(a,L,R) printf(#a"[%d...%d] = ",L,R);\
                        For(_v2,L,R)printf("%d ",a[_v2]);puts("");
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector <int> vi;
LL read(){
    LL x=0,f=0;
    char ch=getchar();
    while (!isdigit(ch))
        f|=ch=='-',ch=getchar();
    while (isdigit(ch))
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
const int N=0x1233,mod=1e9+7;
void Add(int &x,int y){
    if ((x+=y)>=mod)
        x-=mod;
}
void Del(int &x,int y){
    if ((x-=y)<0)
        x+=mod;
}
int Pow(int x,int y){
    int ans=1;
    for (;y;y>>=1,x=(LL)x*x%mod)
        if (y&1)
            ans=(LL)ans*x%mod;
    return ans;
}
int n,cnt;
int a[N];
int Fail[N],delta[N];
vector <int> R[N];
int main(){
    n=read();
    For(i,1,n)
        a[i]=read();
    R[0].clear();
    cnt=0;
    For(i,1,n){
        if (cnt==0){
            if (a[i]){
                Fail[cnt++]=i;
                delta[i]=a[i];
                R[cnt].resize(0);
                R[cnt].resize(i,0);
            }
            continue;
        }
        int sum=0,m=R[cnt].size();
        delta[i]=a[i];
        Fail[cnt]=i;
        For(j,0,m-1)
            Add(sum,(LL)a[i-j-1]*R[cnt][j]%mod);
        Del(delta[i],sum);
        if (!delta[i])
            continue;
        int id=cnt-1,v=i-Fail[id]+(int)R[id].size();
        For(j,0,cnt-1)
            if (i-Fail[j]+(int)R[j].size()<v)
                id=j,v=i-Fail[j]+(int)R[j].size();
        int tmp=(LL)delta[i]*Pow(delta[Fail[id]],mod-2)%mod;
        R[cnt+1]=R[cnt];
        while (R[cnt+1].size()<v)
            R[cnt+1].pb(0);
        Add(R[cnt+1][i-Fail[id]-1],tmp);
        For(j,0,(int)R[id].size()-1)
            Del(R[cnt+1][i-Fail[id]+j],(LL)tmp*R[id][j]%mod);
        cnt++;
    }
    printf("%d\n",(int)R[cnt].size());
    For(i,0,(int)R[cnt].size()-1)
        printf("%d ",R[cnt][i]);
    puts("");
    return 0;
}