浅谈一类 DAG 计数问题
To_string
·
·
算法·理论
第一次写这么长的文章，有问题清指出。
由于本人太弱，只能写一些自己关于这个东西的理解。也有很多很好的题目由于本人太菜没有做，后续做了可能会加上。
有好的题目也欢迎推荐，我可以尝试一下。
::::warning
阅读本文章，需要有一定的图论和容斥基础。
::::
1. 引入
我们考虑一个 DAG，点数很小，我们该如何刻画它；当它点数很大，我们又该怎么刻画？
显然，我们不能将边作为衡量的关键，因为 DAG 的边数是 \mathcal{O}(n^2) 的，加上每条边有 0/1 两种状态，状态总数就是 \mathcal{O}(2^{n^2}) 的，显然不可以接受。
所以，我们应该从 DAG 本身的特性出发。
首先，我们知道 DAG 是能进行 \text{Toposort} 的，那么也就是说，我们一定能找到至少一个入度为 0 的点和出度为 0 的点。
这启发我们对 DAG 进行分层操作，或者说，我们每一次都把 DAG 中入度为 0 的点（或出度为 0）的点删掉，将这些点当作一层，这样剩下来的图也是一个 DAG，这样就有了一个子结构。
::::info[形式化表达]{open}
我们考虑给每一个点附上一个 \text{layer} 标记。初始时，我们将所有的入度为 0 的点的
::::
下面记入度为 $0$ 的点为 **源点**，出度为 $0$ 的点为 **汇点**。
# 2. DAG 计数的一般思路
## 2.1 推导
下面的推导都在 $U$ 全集下的 $S$ 子集进行。
设 $f_S$ 表示在 $S$ 下构造合法 DAG 的方案数。
直观的递推思路是选择一个非空子集 $T \subseteq S$，强制将其中所有的元素为入度为 $0$ 的点，那么剩下的 $S \setminus T$ 必须是一个合法的 DAG。
这样就构造出了一个转移。
但是发现，$T$ 确实所有的点入度为 $0$，但是一旦和 $S \setminus T$ 连起来后，$S\setminus T$ 里面也会有入度为 $0$ 的点，显然会算重。
现在我们就得考虑去重，也就是容斥。
考虑在两者合并后共有 $m$ 个源点，且 $T$ 的大小为 $k$，设容斥系数为 $c(k)$，那么有。
$$
\sum\limits_{k=1}^{m}\binom{m}{k}c(k)=1
$$
由二项式定理知：
$$
(1-1)^m = \sum\limits_{k=0}^{m}\binom{m}{k}(-1)^k
$$
对比两式，很明显知：$c(k)=(-1)^{k-1}$。
由此我们就能推出 DAG 计数的一般形式：
$$
\begin{aligned}
f_S=\sum\limits_{\emptyset \not=T \subseteq S} (-1)^{|T|-1} 2^{E(T,S\setminus T)} f(S\setminus T)
\end{aligned}
$$
其中 $E(A,B)$ 表示从 $A$ 连向 $B$ 的边的数量。
## 2.2 例题
[P6295 有标号 DAG 计数](https://www.luogu.com.cn/problem/P6295)
由于这道题没有题目中给出的边，可以自由选择，所以有哪些点是不强相关的，因为点是可以置换的，我们可以先不管，最后再乘上一个 $n!$ 即可。
也就是说，我们的状态完全没有必要设成集合，而是设成点的数量，也就是设 $f_i$ 表示 $i$ 个点构成 DAG 的方案数。
考虑上述转移。
$$
f_i=\sum\limits_{j=1}^{i} (-1)^{j-1}\binom{i}{j} 2^{j(i-j)} f_j
$$
时间复杂度是 $\mathcal{O}(n^2)$ 的。
而且这样会忽略一个细节，就是这个东西无法保证弱联通，这个先按下不表。
考虑组合意义（至少我是这样认为的），$j(i-j)$ 看作在一堆 $j$ 石子里面摸出一个，再在 $(i-j)$ 个石子里摸出一个的方案数，等价于再 $j+(i-j)=i$ 个里面摸出两个，再减去再同一堆里面摸出两个的方案，用数学语言表达就是：
$$
j(i-j)=\binom{i}{2}-\binom{i-j}{2}-\binom{j}{2}
$$
将式子代回，得到：
$$
f_i=\sum\limits_{j=1}^{i}(-1)^{j-1} \times \frac{2^{\binom{i}{2}}}{2^{\binom{j}{2}} 2^{\binom{j}{2}}} \times \frac{i!}{j!(i-j)!} \times f_j
$$
观察发现，有一部分东西只和 $i$ 有关，有一部分东西和 $j$ 有关，有一部分东西和 $i-j$ 有关。
按照上面的观察整理：
$$
\frac{f_i}{2^\binom{i}{2}i!}=\sum\limits_{j=1}^{i}\frac{(-1)^{j+1}}{2^\binom{j}{2}j! }\times \frac{f_{i-j}}{(i-j)!\times\binom{i-j}{2} }
$$
发现左边的式子明显和右边第二个式子同构。
但是我们还有弱联通这个条件没有解决。有个很经典的结论是 $f$ 的 EGF 是 $ans$ 的 $\operatorname{exp}$。
这完全提示我们使用 EGF 解决这道题。
设 $F(x)=\sum\limits_{i=0}^{\infty}\frac{f_i}{2^\binom{i}{2}i!}$，$G(x)=\sum\limits_{i=0}^{\infty} \frac{(-1)^{j+1}}{2^\binom{j}{2}j! }$。
显然有 $F(x)=F(x)G(x)+1$。
那么 $F(x)=\frac{1}{1-G(x)}$。
接下来就是很简单的操作了，我们设答案的生成函数为 $Ans(x)$，由其组合意义知：$\operatorname{exp}(Ans(x))=F(x)$，反过来 $\ln(F(x))=Ans(x)$。
然后这道题就做完了。
代码就不放了，直接用多项式全家桶就行。
## 2.3 总结
这里我们推出来了 DAG 计数的基本形式，然后也做了一道 DAG 计数的板子题（虽然好像难点不再 DAG 上？），实际上，DAG 计数的基本思路就是：利用 DAG 的无环性质，通过钦定入度为 $0$ 或者出度为 $0$ 的点，将 DAG 分成若干层，构造出子结构进行计数。
# 3. DAG 计数题目
题目难度按本人主观难度递增。
下面的东西会参照 Codeforces 上的题解，给出若干 Hint。
## 3.1 [ARC221B] Two-Powered Sum
[Atcoder](https://atcoder.jp/contests/arc221/tasks/arc221_b)
[Luogu](https://www.luogu.com.cn/problem/AT_arc221_b)
场切题目。
::::info[Hint1]
考虑一下 $A_i=x,A_j=y$，但是 $x$ 的第 $j$ 位为 $1$ 的情况？
::::
::::info[Hint2]
考虑将问题抽象成图，若出现上述的 $x,y$，就连接一条 $x$ 到 $y$ 的有向边。
::::
::::info[Hint3]
考虑图的性质？
::::
如 Hint2 当我们抽象成一张图，一条边 $(x,y)$ 表示 $x$ 操作一定在 $y$ 操作之前。
这里我们考虑从汇点出发，往源点删，为什么呢？因为汇点是无后效性的，它被删掉过后，不会影响前面的东西。
然后发现我们这里可以随意连边，所以集合信息是不重要的，考虑将集合维省略掉。设 $f_i$ 表示目前使用 $i
个点组成的合法 DAG 的个数。
现在我们枚举一下汇点个数 $j$，还有 $j$ 覆盖到了多少个点 $s$，那么显然分配的方案数为 $\begin{Bmatrix}
s
\\
j
\end{Bmatrix}$ 。
然后考虑连边的方式，发现每个点都能连出去 $2^{n-s}$ 条边，所以总的方案数就是 $2^{k(n-s)}$。
带入容斥，得到最终的转移方程：
$$
f_i=
\sum_{s=1}^{i}
\binom{i}{s}
f_{i-s}
\sum_{j=1}^{s}
(-1)^{j-1}
\left\{
\begin{matrix}
s\\
j
\end{matrix}
\right\}
2^{j(i-s)}.
$$
时间复杂度 $\mathcal{O}(n^3)$。
## 3.2 P11714 [清华集训 2014] 主旋律
[Link](https://www.luogu.com.cn/problem/P11714)
写一个自己认为非常顺畅的思维过程吧，也是一个加强了对容斥的理解。
首先，SCC 这种东西是无法被刻画的（或者说很难去很好的刻画），因为它太过于整体化了，没有办法分割成为子问题继续计数。
此时想到正难则反，考虑对于整体不为 SCC 的图计数，那么考虑对于这个图缩点，得到的应该是一个点数大于二的 DAG。
好的，我们设 $E_{S,T}$ 表示所有的从 $S$ 集合连向 $T$ 集合的边的数量，$f_S$ 表示将 $S$ 中所有的元素连成一个 SCC 的方案数，$g_S$ 表示将 $S$ 内的所有点连成若干个 SCC 且 **两个 SCC 之间没有边** 的按 SCC 个数带上容斥系数的和。
这里非常关键，因为当我们给 $g_S$ 带上系数的时候，我们在后面的转移中不用关心 SCC 个数，只关心点集合了。
考虑点集 $S$ 上的所有子图，总方案数为 $2^{E_{S,S}}$ ，现在按照缩点后入度为 $0$ 的 SCC 的并集分类。
若缩点后有 $k$ 个入度为 $0$ 的 SCC ，设他们的点集为 $C_1,C_2,\dots C_k$，那么它们会在每个非空并里面被计算到 $1$ 次，那么有：
$$
\begin{aligned}
2^{E_{S,S}}&=\sum\limits_{\emptyset \not=T\subseteq S} g_T\times2^{E_{T,S/T}+E_{S/T,S/T}}\\
g_S&=2^{E_{S,S}}-\sum\limits_{\emptyset \not=T\subsetneqq S} g_T\times2^{E_{T,S/T}+E_{S/T,S/T}}
\end{aligned}
$$
现在我们已经完成了入度为 $0$ 的 SCC 的容斥，现在我们应该考虑在 $g_S$ 和 $f_S$ 里面去寻找两者的关联。
然后又是非常经典的套路了。
首先考虑 $\operatorname{lowbit}(S)$ 这个点所在的集合 $T$，首先，这个点会贡献一个 $f_T$，然后 $S/T$ 这个集合会提供一个带符号的 $g_{S/T}$，由于多了一个集合，整体会带一个 $-1$ 的容斥系数。
那么根据上面的分析，有：
$$
\begin{aligned}
g_S&=f_S-\sum\limits_{T\subsetneq S \land \operatorname{lowbit}(S)\in T} f_Tg_{S/T}\\
f_S&=g_S+\sum\limits_{T\subsetneq S \land \operatorname{lowbit}(S)\in T} f_Tg_{S/T}
\end{aligned}
$$
现在成功的建立了一个转移，但是需要注意的是，$g$ 的递推用到了所有真子集，然后 $f$ 的递推也用到了所有真子集，但是两者不依赖，可以先转移 $g$ ，再用 $g$ 转移 $f$ ，实现的时候细节一点就行。
现在转移为 $\mathcal{O}(3^n)$，但是我们还有一个 $E$ 没有处理。
这个东西看上去是一个 $4^n$ 的东西，其实使用 $\operatorname{lowbit}$ 加上邻域就能做到 $\mathcal{O}(3^n)$ 。
整体时间复杂度 $\mathcal{O}(3^n)$。
## 3.3 P11834 [省选联考 2025] 岁月
[Link](https://www.luogu.com.cn/problem/P11834)
还没有做出来，补了会加进来。