zcmimi's blog
avatar
zc
2020-07-18 11:27:00
  • 本文总阅读量
查看原题

点击跳转

#include<bits/stdc++.h>
const int N=1200000,P=167772161,G=3,Gi=55924054;
int L,l,r[N],fac[N],inv[N];
void swap(int&x,int&y){int t=x;x=y;y=t;}
int pw(int x,int b){
    int res=1;
    while(b){
        if(b&1)res=1ll*res*x%P;
        b>>=1,x=1ll*x*x%P;
    }
    return res;
}
void getL(int n){
    for(L=1;L<n;L<<=1,++l);
    for(int i=0;i<L;++i)
        r[i]=(r[i>>1]>>1)|((i&1)?(L>>1):0);
}
void ntt(int*A,int typ){
    for(int i=0;i<L;++i)
        if(i<r[i])swap(A[i],A[r[i]]);
    for(int len=1;len<L;len<<=1){
        int Wn=pw(~typ?G:Gi,(P-1)/(len<<1));
        for(int i=0;i<L;i+=len<<1){
            int w=1;
            for(int k=0;k<len;++k){
                int t=1ll*w*A[i+k+len]%P;
                A[i+k+len]=(A[i+k]-t+P)%P;
                A[i+k]=(A[i+k]+t)%P;
                w=1ll*w*Wn%P;
            }
        }
    }
    if(~typ)return;
    for(int i=0,iL=pw(L,P-2);i<L;++i)
        A[i]=1ll*A[i]*iL%P;
}
int s[N],a[N],b[N],g[N];
void mul(int*f,int*g){
    ntt(f,1),ntt(g,1);
    for(int i=0;i<L;++i)f[i]=1ll*f[i]*g[i]%P;
    ntt(f,-1);
}
void solve(int n){
    if(n==1){s[1]=1;return;}
    if(n&1){
        solve(n-1);
        for(int i=n;i;--i)
            s[i]=(s[i-1]+1ll*s[i]*(n-1)%P)%P;
        s[0]=1ll*s[0]*(n-1)%P;
        return;
    }
    int m=n>>1,res=1;
    solve(m);
    for(int i=0;i<=m;++i)
        a[i]=1ll*s[i]*fac[i]%P,
        b[i]=1ll*res*inv[i]%P,
        res=1ll*res*m%P;;
    std::reverse(a,a+m+1);
    getL((m+1)*2);
    mul(a,b);
    for(int i=0;i<=m;++i)
        g[i]=1ll*inv[i]*a[m-i]%P;
    mul(s,g);
    for(int i=m+1;i<L;++i)a[i]=b[i]=g[i]=0;
    for(int i=n+1;i<L;++i)s[i]=0;
}
void init(int n){
    fac[0]=1;
    for(int i=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%P;
    inv[n]=pw(fac[n],P-2);
    for(int i=n-1;i>=0;--i)inv[i]=1ll*inv[i+1]*(i+1)%P;
}
int main(){
    int n;
    scanf("%d",&n);
    init(n+n);
    solve(n);
    for(int i=0;i<=n;++i)
        printf("%d ",s[i]);
}
LG 5408 第一类斯特林数·行
comment评论
Search
search