P6295 有标号 DAG 计数


对 $n$ 个点有标号的有向无环图进行计数,要求:弱连通图(所有的有向边替换为无向边后的图为连通图)。输出答案对 $998244353$ 取模的结果。$1 \le n \le 10^5$。

[集训队作业2013]城市规划


题目描述题目传送门思路套路题。设 fif_ifi​ 表示由 iii 个点所组成的联通无向图个数,gig_igi​ 表示由 iii 个点组成的无向图个数,不保证联通。由于没有重边与自环, iii 个点最多有 (n2)\binom{n}{2}(2n​) 条边,则有 gi=2(n2)g_i = 2^{\b