题解 P5487 【【模板】线性递推+BM算法】
皎月半洒花
2019-08-02 14:38:46
然而是个板子。
因为迄今为止没有什么人写这道题，所以选择自己抛砖引个玉。
学习BM算法推荐以下两个博客
[zzd的博客](https://www.cnblogs.com/zhouzhendong/p/Berlekamp-Massey.html)
[zzq的博客](https://www.cnblogs.com/zzqsblog/p/6877339.html)
~~这俩名字好对称啊~~
然后其实BM的用途就是一个求递推式，但事实上完全可以用来打表。遇到很zz的计数题或者什么，只要脸好一般都是可以找到低次线性递推式子。所以这也不妨是一个黑科技。
之后BM求出来的式子直接拿线性递推跑一下就好。此处如果你写的$k^2 \log n$的暴力常数比较小的话，也是可以跑过去的——卡常数可以参照zzq的博客，他滚了一下空间并且时间上也是很优的。
~~所以不要说我毒瘤啊~~
时限上也是完全够的~~不像某多点求值和快速插值~~。只是注意一下线性递推的时候清零就好。
代码就不上了，都是板子，还是各位自己写吧qwq
____
然而因为没有代码被管理给ban了，所以还是上一下BM算法的板子吧：
```cpp
vector <LL> f[MAXN] ;
int fail[MAXN] ; LL delta[MAXN], now ;
inline void BM(int I){
int i, j ;
for (i = 1 ; i <= I ; ++ i){
for (now = base[i], j = 0 ; j < f[M].size() ; ++ j)
now = (now - base[i - j - 1] * f[M][j] % Mod) % Mod ;
delta[i] = now ; if (!delta[i]) continue ; 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 ;
}
K = f[M].size() ;
for (i = 0 ; i < f[M].size() ; ++ i)
p[i + 1] = (f[M][i] % Mod + Mod) % Mod, cout << p[i + 1] << " " ; puts("") ;
}
。。。。。。
int main(){
int W ; cin >> W >> N ; rr int Len = 1, l = 0, i ;
for (i = 1 ; i <= W ; ++ i) scanf("%lld", &base[i]) ; BM(W) ;
while (Len < (K << 1)) Len <<= 1, ++ l ; F[0] = 1 ; Len <<= 1, ++ l ;
for (i = 0 ; i < Len ; ++ i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (l - 1)) ;
for (i = 1 ; i <= K ; ++ i) G[K - i] = Mod - p[i] ; T[1] = G[K] = 1, reverse(G, G + K + 1), _Inv(G, IG, Len >> 1) ;
reverse(G, G + K + 1), NTT(G, Len, 1), NTT(IG, Len, 1) ;
while(N){
NTT(T, Len, 1) ;
if (N & 1) {
NTT(F, Len, 1) ;
for (i = 0 ; i < Len ; ++ i) F[i] = F[i] * T[i] % Mod ;
NTT(F, Len, -1) ; _Div(F, Len) ;
}
for (i = 0 ; i < Len ; ++ i) (T[i] *= T[i]) %= Mod ; NTT(T, Len, -1) ; _Div(T, Len), N >>= 1 ;
}
for (i = 0 ; i < K ; ++ i) (Ans += (F[i] * base[i + 1]) % Mod) %= Mod ; printf("%lld\n", Ans) ; return 0 ;
}
```