题目描述
对 $n$ 个点有标号的有向无环图进行计数，要求：弱连通图（所有的有向边替换为无向边后的图为连通图）。输出答案对 $998244353$ 取模的结果。
输入格式
一个整数 $T$。
输出格式
共 $T$ 行，第 $i(1\le i\le T)$ 行输出 $n=i$ 时的答案。
输入输出样例 #1
输入 #1
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 \ B(x) = \sum_{i=0}^{+\infty} \frac{(-1)^{i+1}}{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)$。
