问题模型

给定一个有n个元素的数列a,其中第i个元素是aia_i

求一个较短或最短的数列b,假设bm个元素,那么要求满足m<in,ai=j=1maijbj\forall m<i\leq n, a_i = \sum_{j=1}^m a_{i-j} b_j

要求在O(n2)O(n^2)的时间复杂度内解决此问题

Berlekamp_Massey

假设递推式经过c次更新,第i次更新后递推式为R[i]R[i]。初始时,定义R[0]R[0]为空。

假设当前递推式的长度为m,这时候考虑用递推式去算a[i]a[i]是否成立

deltai=aij=1maijR[c][j]delta_i = a_i - \sum_{j=1}^m a_{i-j} R[c][j]

如果deltai=0delta_i=0,那么R[c]R[c]依然合法,不用修改

否则,设failc=ifail_c=i表示递推式R[c]R[c]第一次失效的位置为i

如果c=0c=0,即初始状态。则把R[1]R[1]设置为i0,因为对于空串如果成立,则说明i的元素之前都是0

如果c0c\neq 0,则把问题转换成构造出一个递推式RR',使得对于R+1k<i|R'|+1\leq k < i,有jakjRj=0\sum_j a_{k-j} R'_j = 0,且jaijRj=deltai\sum_j a_{i-j} R'_j = delta_i

0id<c0\leq id < c,设tmp=deltaideltafail[id]tmp = \frac{delta_i}{delta_{fail[id]}},则可以构造

R={0,0,,0,tmp,tmpR[id][1],tmpR[id][2],}R' = \{ 0,0,\cdots, 0, tmp, -tmp\cdot R[id][1],- tmp \cdot R[id][2],\cdots \}

其中开头有ifail[id]1i-fail[id]-10tmp之后是-tmp倍的R[id]R[id]

R[c+1]=R[c]+RR[c+1] = R[c] + R'即可

该构造的正确性证明
首先,当k=nk=n时,显然RR'计算得到的答案为tmpdeltafail[id]=deltaitmp*delta_{fail[id]}=delta_i
其次,当R+1k<i|R'|+1\leq k < i时,R[id]R[id]满足使得和式为0。注意当k变小时,相当于与R[id]R[id]配对的数向左移动了,若R+1k==i1|R'|+1\leq k ==i-1时成立,则R+1kk<i1|R'|+1\leq kk < i-1时也必然成立。因为每个递推式对于任何下标大于该递推式长度,且小于递推式出错位置的aia_i,一定成立

故可以在O(n2)O(n^2)内求出数列aia_i的一个较短线性递推式

若要求最短的线性递推式,则在每次id取值时,每次找minifail[id]+len(R[id])min{i - fail[id] + len(R[id])}即可。易证明,id取值为cnt1cnt-1时最优但是我目前没有发现有标程直接用这个结论,所以如果怕出错的话还是老老实实挨个找最优的id

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;
}

应用场景举例

Educational Codeforces Round 107 (Rated for Div. 2) F