P7364 有标号二分图计数

题目描述

求 $n$ 个点的有标号二分图数目。对每个 $1\le n\le 10^5$ 求出答案。

对 $998244353$ 取模。

输入格式

没有输入。

输出格式

共 $10^5$ 行，第 $i$ 行是 $i$ 个点的有标号二分图数目对 $998244353$ 取模后的值。

输入输出样例 #1

输入 #1

没有输入。

输出 #1

答案的前八行：
1
2
7
41
376
5177
103237
2922446

题解

设黑白染色的有标号二分图的 EGF 为 $F(x)$，有标号二分图的 EGF 为 $G(x)$。

显然有： $$ F(x) \times F(x) = G(x) $$ 因此只要求出 $F(x)$ 即可。

对于 $n$ 个节点的黑白染色的有标号二分图，显然有： $$ f_n = n! 2^{\binom{n}{2}} \sum_{i=0}^{n} \frac{1}{i! 2^{\binom{i}{2}}} \frac{1}{(n-i)! 2^{\binom{n-i}{2}}} $$

通过卷积即可得到 $G(x)$。

时间复杂度 $O(n\log n)$。