有标号二分图计数

求 $n$ 个点的有标号二分图数目

容易想到一个会重复的计算方法：暴力把图剖成两个集合，然后集合间随意连边

$G_n=\displaystyle \sum_{i=0}^n \binom{n} {i}2^{i(n-i)}$

而如果一个二分图包含$t$个连通块，那么在$G$中它会被计算$2^t$次

不妨设$\text{EGF}:$

$H(x)$为$n$个点连通的二分图的数目

$G(x)$为$G_n$的生成函数

$F(x)$为$n$个点二分图生成函数

容易发现$\displaystyle G(x)=\sum \frac{H^i(x)2^i} {i!}=\text{exp}(2H(x))$

而我们要求的答案生成函数$F(x)=\text{exp}(H(x))$

也就是说$F(x)=\sqrt {G(x)}$

而根据组合意义容易发现$\displaystyle i(n-i)=\binom{n} {2}-\binom{i} {2}-\binom{n-i} {2}$，容易通过卷积得到$G(x)$

然后开根即可，实际做的时候注意区分什么时候算的是$\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

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 ll 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]-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;
}

int Div2(int x){ return (x&1?x+P:x)/2; }
V Sqrt(V a){
	if(a.size()==1) return a;
	int n=a.size();
	V b=a; b.resize((n+1)/2),b=Sqrt(b),b.resize(n);
	a=a*~b; a.resize(n);
	rep(i,0,b.size()-1) a[i]+=b[i],Mod1(a[i]);
	rep(i,0,n-1) a[i]=Div2(a[i]);
	return a;
}

int Pow[N],IPow[N];

int main(){
	int n=1e5;
	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,0,n) F[i]=1ll*I[i]*IPow[i]%P;
	F=F*F,F.resize(n+1);
	rep(i,0,n) F[i]=1ll*F[i]*Pow[i]%P;
	F=Sqrt(F);
	rep(i,1,n) printf("%d\n",int(1ll*F[i]*J[i]%P));
}