# 笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭，要么我就注定铸就辉煌。如果有一天，你发现我在平庸面前低了头，请向我开炮。”

### 题解 P5487 【【模板】线性递推+BM算法】

posted on 2019-08-02 14:38:46 | under 题解 |

zzd的博客

zzq的博客

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 ;
}