发布时间：2024-07-31

多项式快速幂

• 首先对k直接取模，然后直接算，复杂度$O(n \log n \log (k \mod 998244353))$

poly qpow(const poly &f,int b){
    int n=f.size();
    poly res{1},a=f;
    res[0]=1;
    init(n<<1);
    res.resize(tot);
    a.resize(tot);
    ntt(res,1),ntt(a,1);
    for(;b;b>>=1){
        if(b&1){
            for(int i=0;i<tot;i++)res[i]=res[i]*a[i]%P;
            ntt(res,-1);
            for(int i=n;i<tot;i++)res[i]=0;
            ntt(res,1);
        }
        for(int i=0;i<tot;i++)a[i]=a[i]*a[i]%P;
        ntt(a,-1);
        for(int i=n;i<tot;i++)a[i]=0;
        ntt(a,1);
    }
    ntt(res,-1);
    return res;
}

• 都取对数$\ln B(x)=k \ln A(x)$，先算出右边，再exp回去
• 复杂度$O(n \log n)$

poly qpow(const poly &f,int b){
    poly lnf=ln(f);
    for(int i=0;i<lnf.size();i++)lnf[i]=lnf[i]*b%P;
    return exp(lnf,f.size());
}