展示型型网站建设,网站建设教程论坛,热门的网站模板下载,动漫设计专升本考什么引入
BM算法主要解决的是根据数列求最短线性齐次递推式的问题在OI中主要辅助打表使用
即#xff1a;已知FFF#xff0c;求序列AAA使得 Fn∑i1mAiFn−i(nm)F_n\sum_{i1}^mA_iF_{n-i} \quad(nm)Fni1∑mAiFn−i(nm)
其中mmm尽量小
算法流程
文中的所有…引入
BM算法主要解决的是根据数列求最短线性齐次递推式的问题在OI中主要辅助打表使用
即已知FFF求序列AAA使得
Fn∑i1mAiFn−i(nm)F_n\sum_{i1}^mA_iF_{n-i} \quad(nm)Fni1∑mAiFn−i(nm)
其中mmm尽量小
算法流程
文中的所有序列下标均从111开始并且为了方便规定000和负下标值均为000
该算法采用增量法即我们求前nnn项的递推式假设已经求出了前n−1n-1n−1项的递推式我们记为AAA,考虑计算加上第nnn项后的递推式A′AA′
设AAA的长度为mmm也就是
mkn,Fk∑i1mAiFk−imkn,F_k\sum_{i1}^mA_iF_{k-i}mkn,Fki1∑mAiFk−i
我们用现在不知道对不对的递推式也就是上一个递推式AAA算出FnF_nFn不知道对不对的值记为Fn′F_nFn′,也就是
Fn′∑i1mAiFn−iF_n\sum_{i1}^mA_iF_{n-i}Fn′i1∑mAiFn−i
如果FnFn′F_nF_nFnFn′,那么这个递推式暂时没有问题继续往后即A′AAAA′A
否则我们把这一位差了多少算出来即
ΔnFn−Fn′\Delta_nF_n-F_nΔnFn−Fn′
注意有可能是负数
现在我们需要修正当前的递推式AAA
仔细观察这个递推式
kn,∑i1mAiFk−iFk∑i1mAiFn−iFn−Δnkn,\sum_{i1}^mA_iF_{k-i}F_k\\ \sum_{i1}^{m}A_iF_{n-i}F_n-\Delta_nkn,i1∑mAiFk−iFki1∑mAiFn−iFn−Δn
和我们希望得到的递推式这里设它长度为m′mm′,显然有m′≥mm\geq mm′≥m
kn,∑i1m′Ai′Fk−iFk∑i1m′Ai′Fn−iFnkn,\sum_{i1}^{m}A_iF_{k-i}F_k\\ \sum_{i1}^{m}A_iF_{n-i}F_nkn,i1∑m′Ai′Fk−iFki1∑m′Ai′Fn−iFn
我们可以考虑给AAA加上一个递推式DDD得到A′AA′容易知道它满足
kn,∑i1m′DiFk−i0∑i1m′DiFn−iΔnkn,\sum_{i1}^{m}D_iF_{k-i}0\\ \sum_{i1}^{m}D_iF_{n-i}\Delta_nkn,i1∑m′DiFk−i0i1∑m′DiFn−iΔn
现在尝试构造一个DDD
我们找到之前的一个匹配失败的递推式RRR设它失败的位置为ppp,当时这个位置的差为Δp\Delta_pΔp。为了避免标识太多看晕我们还是把RRR的长度设为mmm之后的mmm都是指RRR的长度
即
kp,∑i1mRiFk−iFk∑i1mRiFp−iFk−Δpkp,\sum_{i1}^mR_iF_{k-i}F_k\\ \sum_{i1}^mR_iF_{p-i}F_k-\Delta_pkp,i1∑mRiFk−iFki1∑mRiFp−iFk−Δp
重新理一下这个式子的含义
对当前位置kpkpkp,我们从kkk往前面找mmm个数和RRR卷一下然后用FkF_kFk去减都得到了000
唯独ppp不同我们减出来得到了Δp\Delta_pΔp
发现这个跟DDD神似
所以我们考虑这么构造DDD:
开始先放n−p−1n-p-1n−p−1个000进去表示卷积的位置向左平移n−p−1n-p-1n−p−1位,实际上开始与D1D_1D1对应相乘的位置是k−npk-npk−np之后D2,D3,…,DmD_2,D_3,\dots,D_mD2,D3,…,Dm的对应相乘位置不断向左挪
这时我们发现nnn恰好对应到了ppp,也就是RRR中唯一减出来不为000的位置
所以考虑构造这个减法 设xΔnΔpx{\Delta_n\over\Delta p}xΔpΔn
在n−pn-pn−p的位置放一个xxx
然后把RRR的每一位取−x-x−x倍接在后面
这样不考虑xxx的话nnn对应的卷出来是FpF_pFp减去用RRR算出来的Fp′F_pFp′,即Δp\Delta_pΔp,乘上xxx得到Δn\Delta_nΔn。其他位置因为FkFk′F_kF_kFkFk′所以卷出来是000。
也就是
D{0,0,…,0⏟n-p-1个0,x,−xR1,−xR2,…,−xRn}D\{ \underbrace{0,0,\dots,0}_\text{n-p-1个0},x,-xR_1,-xR_2,\dots,-xR_n \}D{n-p-1个00,0,…,0,x,−xR1,−xR2,…,−xRn}
可(bu)以(yong)证明选取最近的RRR一定是最优的
把AAA加上DDD就可以得到A′AA′
复杂度O(n2)O(n^2)O(n2)
模板题
道理我都懂为啥好好的BM模板要加个线性递推
注此代码只有BM部分
#include iostream
#include cstdio
#include cstring
#include cctype
#define MAXN 10005
using namespace std;
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
const int MOD998244353;
inline int add(const int x,const int y){return xyMOD? xy-MOD:xy;}
inline int dec(const int x,const int y){return xy? x-yMOD:x-y;}
typedef long long ll;
inline int qpow(int a,int p)
{int ans1;while (p){if (p1) ans(ll)ans*a%MOD;a(ll)a*a%MOD;p1;}return ans;
}
int F[MAXN],R[MAXN];
int las[MAXN],tmp[MAXN],p,delta;
int main()
{int n,m;nread(),mread();for (int i1;in;i) F[i]read();for (int i1;in;i){int res0;for (int j1;jR[0];j) resadd(res,(ll)R[j]*F[i-j]%MOD);if (resF[i]) continue;if (!R[0]){pi;deltaF[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 j1;jlas[0];j) R[i-pj]dec(R[i-pj],(ll)x*las[j]%MOD);R[0]ilas[0]-p;memcpy(las,tmp,sizeof(las));pi,deltadec(F[i],res);}for (int i1;iR[0];i) printf(%d%c,R[i], \n[iR[0]]);return 0;
}
