学习 Hiengon 大神，开头应该有一句原神语录或者日文歌词，但是我不玩原神，也不是罕见，所以略过。

个人感觉，其实这题的重点不在后面的多项式优化，而在这个容斥系数的推导。这其实展示了一类不太平凡的容斥系数的通用推法。

这个题解本身就是复读论文，后面加点自己的理解。

首先最终的式子是 $f_i = \sum\limits_{0<j<i} f_{i-j}\mathrm C_{i}^{j} 2^{j(i-j)} (-1)^{j-1}$，重点在于那个 $(-1)^{j-1}$ 从哪来。

首先我们有最基本的容斥：

$$g(S) = \sum_{T\subseteq S} f(T)\\f(S) = \sum_{T\subseteq S} (-1)^{|S|-|T|}g(T)$$

可以看作 $\sum\limits_{i=0}^n (-1)^i \mathrm C_{n}^{i}=[n=0]$ 的外在表现，具体的组合双射得参考上面这个的（不知道有没有就是了），反正我不会。这个式子集合关系反过来也是对的，下面要用。

然后我们思考这个题咋做。设 $f(i,S)$ 表示 $i$ 个点，目前零度点集合 恰好 为 $S$ 的方案数，$g(i,S)$ 表示 $i$ 个点，钦定 $S$ 内部均为零度点的方案数。显然有：

$$g(n,S)=\sum_{S\subseteq T} f(n,T)\\f(n,S)=\sum_{S\subseteq T} (-1)^{|T|-|S|} g(n,T)$$

现在我们要算 $g(n,\emptyset)$，直接开始大力推式子：

$$\begin{aligned}g(n,\emptyset) & = \sum_{m=1}^n \sum_{|T|=m} \sum_{T\subseteq S}(-1)^{|T|-|S|} g(n-|S|,\emptyset) 2^{|S|(n-|S|)}\\& = \sum_{S\neq \emptyset} g(n-|S|, \emptyset) 2^{|S|(n-|S|)} \sum_{m=1}^{|S|} (-1)^{|S|-m} \mathrm C_{|S|}^{m}\\& = \sum_{j=1}^{n} g(n-j,\emptyset) \mathrm C_{n}^{j} 2^{j(n-j)} (-1)^{j-1}\end{aligned}$$

每行都解释一下：第一行就是大力展开递推式，第二行交换求和顺序，第三行枚举 $|S|$ 大小直接算，后面那个 $(-1)^{j-1}$ 其实是凑了个 $m=0$ 化二项式定理，然后再减回去。

于是我们就得到了这样一个容斥系数。事实上引起我注意的是最上面的那个最基本的容斥式子，经过之前和 DarkMoon 大神的讨论，发现其实莫反，二项式反演都可以从这个直接理解。

好了，你已经学会有标号 DAG 计数的方法了，快去试试切掉 联合省选2024 d2t2 吧！

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

该题解等待再次审核

首先设 $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$。