........................................................................

该题解等待再次审核

首先设 $f_i$ 为 $i$ 个点的 DAG 数量，枚举其中的 $i-j$ 个点没有入度，然后剩下 $j$ 个点向它们随意连边，但这样会算重，需要在容斥一下，方程是：

$$ f_i = \sum_{j=1}^{i}{(-1)^{j-1} C_i^j 2^{j(i-j)} f_{i-j}}$$

时间复杂度 $O(n^2)$，可过 $n=5000$。

这个式子看起来就很能卷积，不过这个 $2^{j(i-j)}$ 很烦，可以化一下：

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

这样就能把 $j$ 和 $i-j$ 分开了。于是：

$$ f_i = \sum_{j=1}^{i}{(-1)^{j-1} \frac{i!}{j!(i-j)!} 2^{\frac{i^2}{2}-\frac{j^2}{2}-\frac{(i-j)^2}{2}} f_{i-j}}$$

$$   = 2^{\frac{i^2}{2}}i! \sum_{j=1}^{i}{\frac{(-1)^{j-1}}{2^{\frac{j^2}{2}}j!} \frac{f_{i-j}}{2^{\frac{(i-j)^2}{2}}(i-j)!} }$$

设:

$$A(x)=\sum_{i \ge 1}{\frac{(-1)^{i-1}}{2^{\frac{i^2}{2}}i!}x^i}$$

$$F(x)=\sum_{i \ge 0}{\frac{f_i}{2^{\frac{i^2}{2}}i!}x^i}$$

于是：

$$F = A*F +1$$

即：

$$F = \frac{1}{1-A}$$

使用 FFT 卷积，时间复杂度 $O(n\log(n))$，可过 $n=100000$。