P7364 有标号二分图计数

发表于 2025-07-26 更新于 2025-08-10 分类于南京外国语学校 2025 Summer NOI-集训讲义，生成函数阅读次数：
本文字数： 319 阅读时长 ≈ 1 分钟

题目描述

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

对 $998244353$ 取模。

没有输入。

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

没有输入。

设黑白染色的有标号二分图的 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)$ 。