TLE求助
查看原帖
TLE求助
766112
Y__dream楼主2024/12/18 18:20
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e6+10;
const ll mod = 998244353,G=3,inv2=(mod+1)/2;
#define debug(a,len) {for(int _i(0);_i<(len);++_i)printf("%lld ",a[_i]);puts("");}
ll Pow(ll a,ll x){
    ll res=1;
    while(x){
        if(x&1) res=res*a%mod;
        a=a*a%mod;
        x>>=1;
    }
    return res;
}
void change(ll *a,int len){
    static int r[maxn];
    r[0]=0;
    int n=log2(len);
    for(int i=0;i<len;++i){
        r[i]=(r[i>>1]>>1)|((i&1)<<n-1);
        if(i<r[i]) swap(a[i],a[r[i]]);
    }
}
void ntt(ll *a,int n,int rev){
    change(a,n);
    for(int len=2;len<=n;len<<=1){
        ll gn=Pow(G,(mod-1)/len);
        if(rev==-1) gn=Pow(gn,mod-2);
        for(int j=0;j<n;j+=len){
            ll g=1;
            for(int k=j;k<j+(len>>1);++k){
                ll x=a[k],y=g*a[k+(len>>1)]%mod;
                a[k]=(x+y)%mod;
                a[k+(len>>1)]=(x-y+mod)%mod;
                g=g*gn%mod;
            }
        }
    }
    if(rev==-1){
        ll Inv=Pow(n,mod-2);
        for(int i=0;i<n;++i)
            a[i]=a[i]*Inv%mod;
    }
}
void mul(ll *f,int n,ll *g,int m,ll *res){
    static ll x[maxn];
    copy(f,f+n,x);
    copy(g,g+m,res);
    int len=1;
    while(len<=n+m) len<<=1;
    fill(x+n,x+len,0);
    fill(res+m,res+len,0);
    ntt(x,len,1);ntt(res,len,1);
    for(int i=0;i<len;++i)
        res[i]=res[i]*x[i]%mod;
    ntt(res,len,-1);
}
void Inv(ll *f,ll *g,int len){
    static ll x[maxn],y[maxn];
    copy(f,f+len,y);
    fill(y+len,y+(len<<2),0);
    fill(g,g+(len<<2),0);
    g[0]=Pow(y[0],mod-2);
    for(int i=2;i<=len<<1;i<<=1){
        copy(y,y+i,x);
        fill(x+i,x+(i<<1),0);
        ntt(x,i<<1,1);ntt(g,i<<1,1);
        for(int j=0;j<i<<1;++j)
            g[j]=g[j]*(2-x[j]*g[j]%mod+mod)%mod;
        ntt(g,i<<1,-1);
        fill(g+i,g+(i<<1),0);
    }
}
void Div(ll *f,int n,ll *g,int m,ll *Q,ll *R,bool F=1){
    static ll x[maxn],y[maxn];
    copy(f,f+n,x);copy(g,g+m,y);
    reverse(x,x+n);reverse(y,y+m);
    Inv(y,y,n-m+1);
    mul(x,n-m+1,y,n-m+1,Q);
    reverse(Q,Q+n-m+1);
    if(F){
        mul(Q,n-m+1,g,m,x);
        for(int i=0;i<m-1;++i)
            R[i]=(f[i]-x[i]+mod)%mod;
    }
}
void sqrt(ll *f,ll *g,int len){
    static ll x[maxn],tmp[maxn],gg[maxn];
    copy(f,f+len,x);
    fill(x+len,x+(len<<2),0);
    fill(g,g+(len<<2),0);
    g[0]=1;
    for(int i=2;i<=len<<1;i<<=1){
        copy(x,x+i,tmp);
        fill(tmp+i,tmp+(i<<2),0);
        Inv(g,gg,i<<1);
        fill(gg+(i<<1),gg+(i<<2),0);
        ntt(tmp,i<<2,1);ntt(gg,i<<2,1);
        for(int j=0;j<i<<2;++j)
            tmp[j]=tmp[j]*gg[j]%mod;
        ntt(tmp,i<<2,-1);
        for(int j=0;j<i<<1;++j)
            g[j]=inv2*(g[j]+tmp[j])%mod;
        fill(g+i,g+(i<<1),0);
    }
}
void qiudao(ll *f,ll *g,int len){
    for(int i=1;i<len;++i)
        g[i-1]=f[i]*i%mod;
    g[len-1]=0;
}
void jifen(ll *f,ll *g,int len){
    static ll inv[maxn];
    inv[1]=1;
    for(int i=2;i<=len;++i)
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(int i=len-1;i>=1;--i)
        g[i]=f[i-1]*inv[i]%mod;
    g[0]=0;
}
void ln(ll *f,ll *g,int len){
    static ll x[maxn],y[maxn];
    qiudao(f,x,len);
    Inv(f,y,len);
    mul(x,len,y,len,x);
    jifen(x,g,len);
}
void arcsin(ll *f,ll *g,int len){
    static ll x[maxn],tmp[maxn];
    copy(f,f+len,tmp);
    mul(tmp,len,tmp,len,g);
    for(int i=0;i<len;++i)
        g[i]=(mod-g[i])%mod;
    g[0]=(g[0]+1)%mod;
    sqrt(g,g,len);
    Inv(g,g,len);
    qiudao(tmp,x,len);
    mul(g,len,x,len,g);
    jifen(g,g,len);
}
void arctan(ll *f,ll *g,int len){
    static ll x[maxn],tmp[maxn];
    copy(f,f+len,tmp);
    mul(tmp,len,tmp,len,g);
    g[0]=(g[0]+1)%mod;
    Inv(g,g,len);
    qiudao(tmp,x,len);
    mul(g,len,x,len,g);
    jifen(g,g,len);
}
void exp(ll *f,ll *g,int len){
    static ll x[maxn],y[maxn];
    copy(f,f+len,x);
    fill(x+len,x+(len<<1),0);
    g[0]=1;
    g[1]=0;
    for(int i=2;i<=len<<1;++i){
        ln(g,y,i);
        for(int j=0;j<i;++j)
            y[j]=(x[j]-y[j]+mod)%mod;
        y[0]++;
        mul(g,i,y,i,g);
        fill(g+i,g+(i<<1),0);
    }
}
ll a[maxn],b[maxn];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;++i)
        scanf("%lld",&a[i]);
    exp(a,b,n);
    debug(b,n);
    return 0;
}
2024/12/18 18:20
加载中...