Luogu6295 有标号 DAG 计数

题意：求 个点的弱联通有标号 DAG 数目。

弱连通：所有有向边替换为无向边后的图连通。

答案对 取模，，时限 。

---

容易发现，弱连通 DAG 无序组合并分配标号之后就能得到任意的 DAG 图。

那么根据 SET 变换，我们只需求出任意的 DAG 的 EGF，然后取 就能得到答案。

设 为 个点的有标号 DAG 图的方案数。

考虑 DAG 如何拆分成子问题。在对付树时，我们往往去掉根而考虑子树，而对于 DAG，我们要考虑入度为 的节点。

这些点可能有很多个，需要枚举。而且我们很难统计“恰好”有 个入度为 的点的方案，所以还需容斥。

先钦定 个点入度为 ，然后这 个点可以向其余的 个点（仍然是任意 DAG图）任意连边，还要分配标号，能写出 这显然会重复计数，根据经典的容斥加上交错符号即可。

这是卷积的形式，记

（特殊考虑常数项）则有

解得 。再取 就是答案。

复杂度 。