有标号DAG计数

题目大意：求$n$个点有标号弱连通$\text{DAG}$数量

如果你做过类似 「CEOI2019」游乐园 这样常见的$\text{DAG}$计数问题

就会对于统计$\text{DAG}$数量的这个容斥方法十分熟悉

枚举图分层，设当前已经确定的层中点集为$S$，下一层点集为$T$

$dp_{S+T}\leftarrow dp_{S}\times 2^{|S|\cdot |T|}(-1)^{|T|+1}$

其中$|S|\cdot |T|$为层间随意连的边数量，$(-1)^{|T|+1}$是针对分层不唯一的容斥

当然这样统计出的$\text{DAG}$是不连通的

那么我们先考虑用卷积来维护这样的一个图

设分层大小为$a_i,i\in[1,m],n=\sum a_i$，则上式的变化形式就是

$\displaystyle \frac{\displaystyle n!2^{\binom{n} {2} }} {\displaystyle \prod a_i!(-1)^{a_i+1}2^{\binom{a_i} {2} }}$

其中$\displaystyle \binom{n} {2}-\sum \binom{a_i} {2}$就能得出层间边的数量

那么令$\displaystyle F(x)=\sum_{n\ge 1}\frac{(-1)^{n+1} } {n!2^{\binom{n} {2} }}$ ，由于层间有序，答案是

$\displaystyle G(x)=\sum F^i(x)=\frac{1} {1-F(x)}$

求逆一次即可得到$G(x)$，然后补上式子中的系数$\displaystyle 2^{\binom{n} {2} }$

显然不连通的$\text{DAG}$转为连通$\text{DAG}$只需要再求一次$\ln $即可

注意计算的时候是以$\text{EGF}$的形式，最后要补回阶乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
typedef vector <int> V;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

#ifndef ONLINE_JUDGE
#define LOG(...) fprintf(stderr,__VA_ARGS__)
#else
#define LOG(...) 
#endif

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int L=18,N=1<<L|10,P=998244353;

ll qpow(ll x,ll k=P-2) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}

int I[N],J[N];
int rev[N],w[N];
void Init(){
	w[1<<(L-1)]=1;
	int t=qpow(3,(P-1)>>L);
	rep(i,(1<<(L-1))+1,1<<L) w[i]=1ll*w[i-1]*t%P;
	drep(i,(1<<(L-1))-1,1) w[i]=w[i<<1];
	rep(i,J[0]=1,N-1) J[i]=1ll*J[i-1]*i%P;
	I[N-1]=qpow(J[N-1]);
	drep(i,N-1,1) I[i-1]=1ll*I[i]*i%P;
}
int Init(int n){
	int R=1,c=-1;
	while(R<=n) R<<=1,c++;
	rep(i,0,R-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<c);
	return R;
}
void NTT(int n,V &A,int f) {
	static ull a[N];
	if((int)A.size()<n) A.resize(n);
	rep(i,0,n-1) a[rev[i]]=A[i];
	for(int i=1;i<n;i<<=1) {
		int *e=w+i;
		for(int l=0;l<n;l+=i*2) {
			for(int j=l;j<l+i;++j) {
				int t=a[j+i]*e[j-l]%P;
				a[j+i]=a[j]+P-t;
				a[j]+=t;
			}
		}
	}
	rep(i,0,n-1) A[i]=a[i]%P,Mod2(A[i]);
	if(f==-1) {
		reverse(A.begin()+1,A.end());
		ll base=1ll*I[n]*J[n-1]%P;
		rep(i,0,n-1) A[i]=A[i]*base%P;
	}
}

V operator + (V a,const V &b) {
	if(a.size()<b.size()) a.resize(b.size());
	rep(i,0,b.size()-1) a[i]+=b[i],Mod1(a[i]);
	return a;
}
V operator - (V a,const V &b) {
	if(a.size()<b.size()) a.resize(b.size());
	rep(i,0,b.size()-1) a[i]-=b[i],Mod2(a[i]);
	return a;
}
V operator * (V a,V b) {
	int n=a.size()-1,m=b.size()-1;
	int R=Init(n+m);
	NTT(R,a,1),NTT(R,b,1);
	rep(i,0,R-1) a[i]=1ll*a[i]*b[i]%P;
	NTT(R,a,-1),a.resize(n+m+1);
	return a;
}
void println(const V &a){
	for(int i:a) printf("%d ",i);
	puts("");
}
V read(int n){
	V A(n);
	rep(i,0,n-1) A[i]=rd();
	return A;
}
V operator ~ (V a) {
	int n=a.size(),m=(n+1)>>1;
	if(n==1) return {(int)qpow(a[0])};
	V b=a; b.resize(m),b=~b;
	int R=Init(n*2);
	NTT(R,a,1),NTT(R,b,1);
	rep(i,0,R-1) a[i]=(P+2-1ll*a[i]*b[i]%P)*b[i]%P;
	NTT(R,a,-1),a.resize(n);
	return a;
}
V Deriv(V a) {
	rep(i,0,a.size()-2) a[i]=1ll*(i+1)*a[i+1]%P;
	a.pop_back();
	return a;
}
V Integ(V a){
	a.pb(0);
	drep(i,a.size()-1,1) a[i]=1ll*a[i-1]*J[i-1]%P*I[i]%P;
	a[0]=0;
	return a;
}
V Ln(V a){
	int n=a.size();
	a=Deriv(a)*~a;
	return a.resize(n-1),Integ(a);
}
int Div2(int x){ return (x&1?x+P:x)/2; }
int Pow[N],IPow[N];

int main(){
	int n=rd();
	Init();
	Pow[0]=Pow[1]=IPow[0]=IPow[1]=1;
	for(int i=2,x=2,y=(P+1)/2;i<N;i++,x*=2,Mod1(x),y=Div2(y)) {
		Pow[i]=1ll*Pow[i-1]*x%P;
		IPow[i]=1ll*IPow[i-1]*y%P;
	}
	V F(n+1);
	rep(i,1,n) {
		F[i]=1ll*I[i]*IPow[i]%P;
		if(~i&1) F[i]=-F[i],Mod2(F[i]); // 这个是容斥系数 
		F[i]=P-F[i];// 这个是1-F
	}
    // 这个是1-F
	F[0]=1;
	F=~F;
	rep(i,0,n) F[i]=1ll*F[i]*Pow[i]%P;
    // 补回系数，然后做一次ln
	F=Ln(F);
	rep(i,0,n) F[i]=1ll*F[i]*J[i]%P;
	rep(i,1,n) printf("%d\n",F[i]);
}