P6295 有标号 DAG 计数

题目描述

对 $n$ 个点有标号的有向无环图进行计数，要求：弱连通图（所有的有向边替换为无向边后的图为连通图）。输出答案对 $998244353$ 取模的结果。

输入格式

一个整数 $T$ 。

输出格式

共 $T$ 行，第 $i (1 \leq i \leq T)$ 行输出 $n = i$ 时的答案。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

第一个点 $T = 2000$ 。

第二个点 $T = 100000$ 。

题解

考虑先求出任意有标号 DAG，然后对 EGF 求一下 $\ln$ 即可得到弱连通的 DAG 数量。

设 $f (i)$ 表示 $i$ 个点的有标号 DAG 数量，则：

f (i) = \sum_{j = 1}^{i} C_{i}^{j} \times f (i - j) \times 2^{j (i - j)} \times (- 1)^{j + 1}

枚举至少有 $j$ 个入度为 0 的点的个数（因为 DAG，所以一定存在至少一个入度为 0 的点），剩余的 $i - j$ 个点构成 DAG，这 $j$ 个点到另外 $i - j$ 个点任意选择连不连边。但是注意到这个 $j$ 没有保证恰好，只是保证最少有 $j$ 个入度为 0 的点，所以还需要容斥一下。

然后把 $C_{i}^{j}$ 和 $2^{j (i - j)}$ 分别解决掉就可以了。

$C_{i}^{j}$ 我们再熟悉不过，求两边的 EGF 即可消去。

另一个 trick 也是常用的：

j \times (i - j) = C_{i}^{2} - C_{j}^{2} - C_{i - j}^{2}

所以：

2^{j (i - j)} = \frac{2^{C_{i}^{2}}}{2^{C_{j}^{2}} \times 2^{C_{i - j}^{2}}}

按照和 EGF 相同的策略，我们设两个生成函数：

A (x) = \sum_{i = 0}^{+ \infty} \frac{f (i)}{i! \times 2^{C_{i}^{2}}} x^{i}

那么改写最上面的式子，就有：

A (x) = A (x) B (x) + 1

最后的 $+ 1$ 是因为 $f_{0} = 1$ 。

解得：

A (x) = \frac{1}{1 - B (x)}

计算可得 $A (x)$ 的值。

最后考虑弱连通的条件，不弱连通的 DAG 肯定由若干个连通分量组合。设 $f (i)$ 的 EGF 为 $F (x)$ ，弱连通 DAG 的 EGF 为 $H (x)$ ，那么按照 EGF 的组合意义：

F (x) = \exp (H (x))

所以：

H (x) = \ln (F (x))

总的过程是一次求逆和一次 $\ln$ ，时间复杂度 $O (n \log n)$ 。