【学习笔记】Berlekamp-Massey算法

Berlekamp-Massey算法用于在$O(n^2)$的时间内求解数列的递推式。

形式化地讲,给定 $a_i(i=1,2,3…n-1,n)$,求一组 $b_j(j=1,2,3…m)$,满足:

其中或许会有条件限制$m$最小。

神仙构造

考虑增量构造。即已知满足前 $i - 1$ 项的递推式,如何求出也满足第 $i$ 项的。

定义 $\Delta_i$ 表示第 $i$ 项与当前递推式之间的差值,$\rm F$ 为当前暂时满足条件的递推式 $\{f_i\}$。

那么定义:

考虑如果 $\Delta_i=0$ 那么就不需要管,现在考虑 $\Delta_i \not =0$ 的情况。

考虑一个大体的构造思想,我们最后构造出的 $\rm F$ 尽量是让前面满足的递推关系满足,并且使得新加进来的一组关于 $i$ 的递推关系也满足。

考虑令 $\mathrm{F}_k$ 表示修改过 $k$ 次之后的递推式,$\mathrm{fail}_k$ 表示第 $k$ 个版本的递推式是哪个 $i$ 开始失配的。不妨记算完 $a_{i-1}$ 的 $\rm F$ 是第 $q$ 个版本,即 $\rm F_q$

那么考虑我们需要构造一个这样的 $\mathrm F’:\{f’_1,f’_2,\dots f_{m’}’\}$ ,使得

同时有:

那么显然令 $\mathrm{F}_{q+1}=\mathrm{F_q}+\mathrm{F’}$ 就是答案。

考虑这么一种构造方式:随便选一个历史版本 $o,1\leq o\leq q$ ,令 $\alpha=\frac{\Delta_i}{\Delta_o}$ ,那么 $\rm F’$ 就是:

其中前缀 $0$ 的个数为 $i-\mathrm{fail}_o-1$ ,最后 $\mathrm {fail} _o$ 项是 $\rm F\it _o$ 整体乘上了 $\alpha$。

思考这样的可行性,设 $p’\in[1,i]\cap\mathbb Z$ ,那么有:

发现刚好满足要求。于是可知 $\mathrm{F}_{q+1}=\mathrm{F_q}+\mathrm{F’}$ 即为答案。

那么考虑如何求最短递推式。发现 $1\leq o\leq q$ 的选取没有限制,所以选 $|\mathrm{F}_o|+i-\mathrm{fail}_o$ 最小的即可。

实现部分

大概还是很显然的?过程都很清晰,就是模拟了一遍而已。

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
int fail[MAXN] ; 
vector <LL> f[MAXN] ;
LL delta[MAXN], now ;
inline void BM(int I){
int i, j ;
for (i = 1 ; i <= I ; ++ i){
now = base[i] ;
for (j = 1 ; j <= f[M].size() ; ++ j)
now = now - base[i - j] * f[M][j - 1] % Mod ;
delta[i] = (now % Mod + Mod) % Mod ;
if (!delta[i]) continue ; else fail[M] = i ;
if (!M) {
f[++ M].resize(i) ;
delta[i] = base[i] ; continue ;
}
int Id = M - 1 ;
v = f[Id].size() - fail[Id] + i ;
for (j = 0 ; j < M ; ++ j)
if (i - fail[j] + f[j].size() < v)
Id = j, v = i - fail[j] + f[j].size() ;
f[M + 1] = f[M] ; ++ M ;
while (f[M].size() < v) f[M].push_back(0) ;
LL mul = delta[i] * expow(delta[fail[Id]], Mod - 2) % Mod ;
(f[M][i - fail[Id] - 1] += mul) %= Mod ;
for (j = 0 ; j < f[Id].size() ; ++ j)
(f[M][i - fail[Id] + j] -= mul * f[Id][j]) %= Mod ;
}
for (i = 0 ; i < f[M].size() ; ++ i)
p[i + 1] = (f[M][i] % Mod + Mod) % Mod, cout << p[i + 1] << " " ;
}

然后就没有然后了