Luogu

分析

设 $f_i$ 为 $i$ 个点的 DAG 数量。

一个想法是枚举入度为 $0$ 的点的数量，有
$$
f_n=\sum_{i=1}^n{n\choose i}f_{n-i}2^{i(n-i)}
$$
然而这样子是不行的，因为会有一些其它的点入度为 $0$。

所以要容斥，有
$$
f_n=\sum_{i=1}^n(-1)^{i-1}{n\choose i}f_{n-i}2^{i(n-i)}
$$
这样子是 $\mathcal{O}(n^2)$ 的。

考虑把 $2^{i(n-i)}$ 拆掉，变成 $2^{\frac{n^2}{2}-\frac{i^2}{2}-\frac{(n-i)^2}{2}}$，则
$$
f_n=\sum_{i=1}^n(-1)^{i-1}{n\choose i}f_{n-i}2^{\frac{n^2}{2}-\frac{i^2}{2}-\frac{(n-i)^2}{2}}
$$
设 $t=\sqrt{2}$，继续拆
$$
\begin{aligned}
f_n&=\sum_{i=1}^n(-1)^{i-1}\frac{n!}{i!(n-i)!}f_{n-i}t^{n^2-i^2-(n-i)^2}\\
\frac{f_n}{t^{n^2}n!}&=\sum_{i=1}^n\frac{(-1)^{i-1}}{t^{i^2}i!}\times\frac{f_{n-i}}{t^{(n-i)^2}(n-i)!}
\end{aligned}
$$
构造 EGF
$$
\begin{aligned}
F(x)&=\sum_{i=0}^{+\infty}\frac{f_i}{t^{i^2}}\frac{x^i}{i!}\\
G(x)&=\sum_{i=1}^{+\infty}\frac{(-1)^{i-1}}{t^{i^2}}\frac{x^i}{i!}
\end{aligned}
$$
那么有
$$
F(x)=F(x)G(x)+1
$$
即
$$
F(x)=\frac{1}{1-G(x)}
$$
多项式求逆即可。

现在还要求弱连通，那么把 $F(x)$ 求个多项式 $\ln$ 即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=400000+10;
const int mod=998244353,sqrt2=882049182,invsqrt2=441024591;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int r[N];
void NTT(int* A,int n,int op) {
    for (int i=0;i<n;++i) if (i<r[i]) swap(A[i],A[r[i]]);
    for (int i=1;i<n;i<<=1) {
        int rot=qpow(op==1?3:332748118,(mod-1)/(i<<1));
        for (int j=0;j<n;j+=i<<1)
            for (int k=0,w=1;k<i;++k,w=1ll*w*rot%mod) {
                int x=A[j+k],y=1ll*w*A[j+k+i]%mod;
                A[j+k]=(x+y)%mod,A[j+k+i]=(x-y+mod)%mod;
            }
    }
    if (op==-1) { int inv=qpow(n,mod-2);
        for (int i=0;i<n;++i) A[i]=1ll*A[i]*inv%mod;
    }
}
int NTT_init(int n) {
    int lim=1,l=-1;
    for (;lim<=n;lim<<=1,++l);
    for (int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<l);
    return lim;
}

void getinv(int* F,int* G,int n) {
    static int A[N],B[N];
    if (n==1) { G[0]=qpow(F[0],mod-2); return; }
    getinv(F,G,n>>1);
    for (int i=0;i<n;++i) A[i]=F[i],B[i]=G[i];
    int lim=NTT_init(n);
    NTT(A,lim,1),NTT(B,lim,1);
    for (int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod*B[i]%mod;
    NTT(A,lim,-1);
    for (int i=0;i<n;++i) G[i]=(2ll*G[i]-A[i]+mod)%mod;
    for (int i=0;i<lim;++i) A[i]=B[i]=0;
}

void getderi(int* F,int* G,int n) {
    for (int i=1;i<n;++i) G[i-1]=1ll*F[i]*i%mod;
    G[n-1]=0;
}
void getinte(int* F,int* G,int n) {
    for (int i=1;i<n;++i) G[i]=1ll*F[i-1]*qpow(i,mod-2)%mod;
    G[0]=0;
}

void getln(int* F,int* G,int n) {
    static int A[N],B[N];
    getderi(F,A,n),getinv(F,B,n);
    int lim=NTT_init(n);
    NTT(A,lim,1),NTT(B,lim,1);
    for (int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod;
    NTT(A,lim,-1);
    getinte(A,G,n);
    for (int i=0;i<lim;++i) A[i]=B[i]=0;
}

int fac[N],ifac[N],f[N],g[N],h[N];

int main() {
    int n=read();
    fac[0]=1;
    for (int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n],mod-2);
    for (int i=n;i;--i) ifac[i-1]=1ll*ifac[i]*i%mod;
    for (int i=0;i<=n;++i) {
        int w=1ll*ifac[i]*qpow(invsqrt2,1ll*i*i%(mod-1))%mod;
        g[i]=(i&1)?mod-w:w;
    }
    int lim=1;
    for (;lim<=n;lim<<=1);
    getinv(g,h,lim);
    for (int i=0;i<=n;++i)
        h[i]=1ll*h[i]*qpow(sqrt2,1ll*i*i%(mod-1))%mod;
    getln(h,f,lim);
    for (int i=1;i<=n;++i) printf("%d\n",1ll*f[i]*fac[i]%mod);
    return 0;
}