$\text{O}(n \log n)$ 多项式运算

贴个老板子

namespace Modsqrt{
 
    #define ll long long
 
    ll w2;
 
    struct CP{
        ll x,y;
        CP() {}
        CP(ll x,ll y):x(x),y(y) {}
        CP operator *(const CP &a) const{
            ll X=(x*a.x+y*a.y%mod*w2)%mod;
            ll Y=(x*a.y+y*a.x)%mod;
            return CP(X,Y);
        }
    };
 
    inline CP CP_qpow(CP a,int b){
        CP ans=CP(1,0);
        for(;b;b>>=1){
            if(b&1)ans=ans*a;
            a=a*a;
        }
        return ans;
    }
 
    inline ll modsqrt(ll x){
        srand(time(0));
        ll y=1ll*rand()*rand()%mod;
        while(qpow(w2=(y*y+mod-x)%mod,(mod-1)>>1)==1)
            y=1ll*rand()*rand()%mod;
        CP ans=CP_qpow(CP(y,1),(mod+1)>>1);
        return min(ans.x,mod-ans.x);
    }
 
    #undef ll
 
}
 
using namespace Modsqrt;
 
long long inv[maxn],frac[maxn],invf[maxn];
 
inline void Init_Inv(int N){
    frac[0]=1;
    for(int i=1;i<=N;i++)frac[i]=frac[i-1]*i%mod;
    invf[N]=qpow(frac[N],mod-2);
    for(int i=N;i>=1;i--)invf[i-1]=invf[i]*i%mod;
    for(int i=1;i<=N;i++)inv[i]=invf[i]*frac[i-1]%mod;
}
 
inline void init(int N){
    Init_Inv(N);
}
 
namespace Polyn{
 
    #define G 3
 
    #define ll long long
 
    int lstn,rev[maxn];
 
    long long g[2][33];
 
    inline void cpy(int N,ll *a,ll *b){
        for(int i=0;i0){
            for(int i=N-1;i>=len;i--)a[i]=a[i-len];
            for(int i=len-1;i>=0;i--)a[i]=0;
        }
        else {
            len=-len;
            for(int i=0;i=1;i--){
            g[0][i]=g[0][i+1]*g[0][i+1]%mod;
            g[1][i]=g[1][i+1]*g[1][i+1]%mod;
        }
    }
 
    inline void init(int N){
        if(lstn==N)return;
        lstn=N;
        for(int i=1;i>1)]>>1)|(i&1?(N>>1):0);
    }
 
    inline void Der(int N,ll *f){
        for(int i=1;i>1,A,ans);
            cpy(len,B,f);
            Mul(len,A,B);
            clr(len>>1,A);
            cpy(len,B,ans);
            Mul(len,A,B);
            for(int i=(len>>1);i=MOD)return;
        cpy(n,ans,f);
        mve(n,-x,ans);
        int m=MOD-x;
        if(ans[0]>1){
            ll inv0=qpow(ans[0],mod-2);
            for(int i=0;i1)Mul(MOD,ans,qpow(f[x],k1));
    }
 
    #undef ll
 
    #undef G
 
}
 
long long A[maxn];
 
struct P{
 
    #define ll long long
 
    int n;
 
    ll f[maxn];
 
    inline void Read(){
        for(int i=0;i();
    }
 
    inline void Print(){
        for(int i=0;i