_皎月半洒花 的博客

_皎月半洒花 的博客

反抗命运的镇魂曲停歇之前,你绝对不可以说我懦弱,绝对不可以说我没有殊死一搏。

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

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

然而是个板子。

因为迄今为止没有什么人写这道题,所以选择自己抛砖引个玉。

学习BM算法推荐以下两个博客

zzd的博客

zzq的博客

这俩名字好对称啊

然后其实BM的用途就是一个求递推式,但事实上完全可以用来打表。遇到很zz的计数题或者什么,只要脸好一般都是可以找到低次线性递推式子。所以这也不妨是一个黑科技。

之后BM求出来的式子直接拿线性递推跑一下就好。此处如果你写的 $k^2 \log n$ 的暴力常数比较小的话,也是可以跑过去的——卡常数可以参照zzq的博客,他滚了一下空间并且时间上也是很优的。

所以不要说我毒瘤啊

时限上也是完全够的不像某多点求值和快速插值。只是注意一下线性递推的时候清零就好。

代码就不上了,都是板子,还是各位自己写吧qwq


然而因为没有代码被管理给ban了,所以还是上一下BM算法的板子吧:

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