$Berlekamp-Massey$模板
已知数列前几项为A，求出数列递推式B。
——————————————————
|
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 |
vector<int> BM(vector<int> &A) { vector<int> B,S; int best=0,cnt=0; for (int i=0;i<(int)A.size();i++) { ll x=A[i]; for (int j=0;j<(int)B.size();j++) x=(x-(ll)B[j]*A[i-j-1]%mo+mo)%mo; delta[i]=x; if (!x) continue; fail[cnt++]=i; if (B.empty()) { B.resize(i+1); best=cnt-1; continue; } ll k=x*mi(delta[fail[best]],mo-2)%mo; vector<int> C; C.resize(i-fail[best]-1); C.push_back(k); for (int j=0;j<(int)S.size();j++) C.push_back((mo-k*S[j]%mo)%mo); if (C.size()<B.size()) C.resize(B.size()); for (int j=0;j<(int)B.size();j++) C[j]=(C[j]+B[j])%mo; if (B.size()<=i-fail[best]+S.size()) best=cnt-1,S=B; B=C; } return B; } |
