引入

BM算法主要解決的是根據(jù)數(shù)列求最短線性齊次遞推式的問題在OI中主要輔助打表使用

即：已知$F$，求序列$A$使得

$$F_n=\sum _{i=1}^m{A}_i{F}_{n?i}(n>m)$$

其中$m$盡量小

算法流程

文中的所有序列下標均從$1$開始，并且為了方便規(guī)定$0$和負下標值均為$0$

該算法采用增量法，即我們求前$n$項的遞推式，假設已經(jīng)求出了前$n?1$項的遞推式，我們記為$A$,考慮計算加上第$n$項后的遞推式$A^{\prime }$

設$A$的長度為$m$，也就是

$$m<k<n,F_k=\sum _{i=1}^m{A}_i{F}_{k?i}$$

我們用現(xiàn)在不知道對不對的遞推式，也就是上一個遞推式$A$，算出$F_n$不知道對不對的值，記為$F_n^{\prime }$,也就是

$$F_n^{\prime }=\sum _{i=1}^m{A}_i{F}_{n?i}$$

如果$F_n=F_n^{\prime }$,那么這個遞推式暫時沒有問題，繼續(xù)往后，即$A^{\prime }=A$

否則我們把這一位差了多少算出來，即

$${\Delta }_n=F_n?F_n^{\prime }$$

注意有可能是負數(shù)

現(xiàn)在我們需要修正當前的遞推式$A$

仔細觀察這個遞推式

$$\begin{gathered} k<n,\sum _{i=1}^m{A}_i{F}_{k?i}=F_k \\ \sum _{i=1}^m{A}_i{F}_{n?i}=F_n?{\Delta }_n \end{gathered}$$

和我們希望得到的遞推式，這里設它長度為$m^{\prime }$,顯然有$m^{\prime }\ge m$

$$\begin{gathered} k<n,\sum _{i=1}^{m^{\prime }}{A}_i^{\prime }{F}_{k?i}=F_k \\ \sum _{i=1}^{m^{\prime }}{A}_i^{\prime }{F}_{n?i}=F_n \end{gathered}$$

我們可以考慮給$A$加上一個遞推式$D$得到$A^{\prime }$，容易知道它滿足

$$\begin{gathered} k<n,\sum _{i=1}^{m^{\prime }}{D}_i{F}_{k?i}=0 \\ \sum _{i=1}^{m^{\prime }}{D}_i{F}_{n?i}={\Delta }_n \end{gathered}$$

現(xiàn)在嘗試構(gòu)造一個$D$

我們找到之前的一個匹配失敗的遞推式$R$，設它失敗的位置為$p$,當時這個位置的差為${\Delta }_p$。為了避免標識太多看暈，我們還是把$R$的長度設為$m$，之后的$m$都是指$R$的長度

即

$$\begin{gathered} k<p,\sum _{i=1}^m{R}_i{F}_{k?i}=F_k \\ \sum _{i=1}^m{R}_i{F}_{p?i}=F_k?{\Delta }_p \end{gathered}$$

重新理一下這個式子的含義：

對當前位置$k<p$,我們從$k$往前面找$m$個數(shù)和$R$卷一下，然后用$F_k$去減，都得到了$0$

唯獨$p$不同，我們減出來得到了${\Delta }_p$

發(fā)現(xiàn)這個跟$D$神似

所以我們考慮這么構(gòu)造$D$:

開始先放$n?p?1$個$0$進去，表示卷積的位置向左平移$n?p?1$位,實際上開始與$D_1$對應相乘的位置是$k?n+p$，之后$D_2,D_3,\dots ,D_m$的對應相乘位置不斷向左挪

這時我們發(fā)現(xiàn)$n$恰好對應到了$p$,也就是$R$中唯一減出來不為$0$的位置

所以考慮構(gòu)造這個減法 設$x=\frac{{\Delta }_n}{\Delta p}$

在$n?p$的位置放一個$x$

然后把$R$的每一位取$?x$倍接在后面

這樣不考慮$x$的話，$n$對應的卷出來是$F_p$減去用$R$算出來的$F_p^{\prime }$,即${\Delta }_p$,乘上$x$得到${\Delta }_n$。其他位置因為$F_k=F_k^{\prime }$，所以卷出來是$0$。

也就是

$$D=\{\underset{\text{n-p-1個0}}{0,0,\dots ,0},x,?x{R}_1,?x{R}_2,\dots ,?x{R}_n\}$$

可(bu)以(yong)證明，選取最近的$R$一定是最優(yōu)的

把$A$加上$D$就可以得到$A^{\prime }$

復雜度$O(n^2)$

模板題

道理我都懂，為啥好好的BM模板要加個線性遞推

注：此代碼只有BM部分

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #define MAXN 10005 using namespace std; inline int read() {int ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans; } const int MOD=998244353; inline int add(const int& x,const int& y){return x+y>=MOD? x+y-MOD:x+y;} inline int dec(const int& x,const int& y){return x<y? x-y+MOD:x-y;} typedef long long ll; inline int qpow(int a,int p) {int ans=1;while (p){if (p&1) ans=(ll)ans*a%MOD;a=(ll)a*a%MOD;p>>=1;}return ans; } int F[MAXN],R[MAXN]; int las[MAXN],tmp[MAXN],p,delta; int main() {int n,m;n=read(),m=read();for (int i=1;i<=n;i++) F[i]=read();for (int i=1;i<=n;i++){int res=0;for (int j=1;j<=R[0];j++) res=add(res,(ll)R[j]*F[i-j]%MOD);if (res==F[i]) continue;if (!R[0]){p=i;delta=F[i];R[0]=i;continue;}memcpy(tmp,R,sizeof(tmp));int x=(ll)dec(F[i],res)*qpow(delta,MOD-2)%MOD;R[i-p]=add(R[i-p],x);for (int j=1;j<=las[0];j++) R[i-p+j]=dec(R[i-p+j],(ll)x*las[j]%MOD);R[0]=i+las[0]-p;memcpy(las,tmp,sizeof(las));p=i,delta=dec(F[i],res);}for (int i=1;i<=R[0];i++) printf("%d%c",R[i]," \n"[i==R[0]]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的感性理解Berlekamp-Massey算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。