[Hard] P11714 [清华集训 2014] 主旋律

· · 题解

简要题意

给定一个 n 个点 m 条边的有向图，你需要求出其的边集数，使得断掉边集中的所有边后，整张图强联通。答案对 10^9+7 取模。

## 思路 extreme hard 的状压 dp 题，做这道题前最好做一下 [P6846 \[CEOI 2019\] Amusement Park](https://www.luogu.com.cn/problem/P6846)，没做也没有关系。 约定： - $U$ 表示全集 $\{1,2,\cdots,n\}$。$S-T$ 表示 $T$ 在全集 $S$ 下的补集 $\complement_S T$。 - $p(S)$ 表示点集 $S$ 的导出子图的边数，$p(S\to T)$ 表示满足 $u\in S,v\in T$ 的有向边 $(u,v)$ 的数量。 ### Part 1 首先设 $f(S)$ 表示点集为 $S$ 的强联通图数量，那么答案就是 $f(U)$，考虑转移。 首先我们如何刻画强联通题图（以下简称 SCG）这个性质，发现我们趁手的工具非常少，不过刻画强联通分量（以下简称 SCC）的关系工具是存在的，就是缩点。假如我们将整张图缩点后只剩下一个点，那么肯定是 SCG。正难则反，不妨考虑缩点后形成了 $\geq 2$ 个点的方案数。 缩点后，整张图变成一个 DAG，可以考虑一些对 DAG 计数的方法。 计算 DAG 的数量有一个常见的状态 dp 的方法，就是枚举拓扑序最小的点集，按照拓扑序转移（如果你不熟悉，请尝试完成前面提到的 Amusement Park 一题）。这道题不是计算 DAG，但是可以将一个 SCC 看成一个点，就是计算 DAG 了。 转移？不妨枚举拓扑序最小的所有 SCC 的并集 $T$，可以得到一个残缺的转移方程（其中 $\square(T)$ 表示我们需要补全的部分）： $$ f(S)=2^{p(S)}-\sum_{T\subseteq S,T\neq\varnothing} 2^{p(T\to S-T)+p(S-T)} \cdot \large\square(T) $$ 稍微解释一下，$2^{p(S)}$ 即点集为 $S$ 的子图的方案数。$p(T\to S-T)$ 和 $p(S-T)$ 都是不在拓扑序最小的 SCC 的点集的边，无需考虑，所以可以任意选择。 ### Part 2 我们需要补全上一部分中的 $\square(T)$，依据 Amusement Park 一题，很容易写出下面的式子： $$ \square(T)=\sum_{k=1}^{|T|}(-1)^{k+1} s(T,k) $$ 其中 $s(T,k)$ 表示将点集 $T$ 的子图为 $k$ 的互不连通的 SCC 的方案数。特别地，我们令 $T=S$ 时 $k\neq 1$ 表示只有一个连通块的方式是禁止的。 > 简单介绍一下为什么我们这么写。 > > 关注到我们必须保证每次枚举出来的都是恰好拓扑序最小（入度为 $0$）的点，如果不是则导致计算混乱，不过求出任意一个入度为 $0$ 的子集对应的方案数是容易的。所以不妨引入容斥。但是我不太会容斥，所以可以用一些公式化容斥的东西，比如子集反演。注意下面的推导都是基于 DAG 而不是本题的。 > > 如果设 $g(T)$ 表示拓扑序最小，$f(T)$ 表示精确覆盖拓扑序最小。可以写出 $g(T)=\sum_{A\subseteq T} f(T)$，反演得到 $f(T)=\sum_{T\subseteq A}(-1)^{|A|-|T|}g(A)$。 > > 故 $g(S)=\sum_{T\subseteq S}\sum_{T\subseteq A}(-1)^{|A|-|T|}g(A)$，稍加变换，得到 $g(S)=\sum_{A\subseteq S}g(A) \sum_{T\subseteq A}(-1)^{|A|-|T|}$，进一步化简，得到 $g(S)=\sum_{A\subseteq S} g(A)\cdot (-1)^{|A|}\cdot \sum_{k=1}^{|A|}\binom{|A|}{k}(-1)^k$。 > > 注意到由于空集没有合适的定义，所以不考虑空集。 > > 根据二项式定理，$\sum_{k=1}^{|A|}\binom{|A|}{k}(-1)^k=(-1+1)^{|A|}-\binom{|A|}{0}(-1)^0=-1$，所以最后得到 $g(S)=\sum_{A\subseteq S} (-1)^{|A|+1}$。 > > 本题也需要计算 DAG 结构，所以可以迁移容斥的形式，所以自然要拆分 SCC 数来决定容斥系数 $(-1)^{|A|+1}$。 现在需要求出 $s(T,k)$，不过这样发现即使可以 $O(1)$ 求出（况且这也比较困难），大概率也无法通过本题了，所以更加务实的想法是直接求出 $\square(T)$。，由于这不再是空缺的，所以赐给它一个字母，用 $h(T)$ 来表示它。 现在将 $h(T)$ 回代，得到 $f(T)$ 的新转移方程： $$ f(S)=2^{p(S)}-\sum_{T\subseteq S,T\neq\varnothing} 2^{p(T\to S-T)+p(S-T)} \cdot h(T) $$ ### Part 3 我们需要求出 $h(T)$，一种自然的方法是枚举其中一个 SCC，不过这很容易算重。不过有一种更加简单的方法：先确定 $T$ 中某一个点 $u$，然后枚举 $u$ 的 SCC，可以转移： $$ -h(S)=\sum_{T\subseteq S-\{u\}} f(T\cup\{u\})h(S - T\cup\{u\}) $$ 当然这个形式不太美观，可以改一改： $$ -h(S)=\sum_{T\subseteq S-\{u\}} h(T)f(S-T) $$ 解释一下，$T$ 是与 $u$ 在同一个 SCC 的点集（更改后为不在同一个 SCC 的点集），$h(S)$ 前面有负号，是因为容斥系数的影响，多了一个 SCC 会取反。这个卷积的形式比较好理解，就不讲了。 看起来这个形式很好，不是吗？不过有两点遗留问题： - 在 $S=T$ 时，$h(T)$ 不能取到大小为 $1$。 - 在计算 $f(S)$ 时，如果枚举到了 $T=\varnothing$，那么同时也需要用到 $f(S)$ 的值，导致转移成环。 这两个问题单独出现，都是难以解决的，不过本题中它们一起出现了，$T=\varnothing$ 就是大小为 $1$ 的情况啊！将式子稍作改写（钦定 $h(\varnothing)=1$，这是转移正确性的需要）： $$ -h(S)=f(S)+\sum_{T\subseteq S-\{u\},T\neq\varnothing} h(T)f(S-T) $$ 于是只要计算 $h(S)$ 时先不计算 $f(S)$ 一项，计算完 $f(S)$ 后加上即可。 ### Part 4 如何实现本题？ 对于边界，$f(\{u\})=h(\{u\})=1$，然后是时间复杂度： - $e(S)$ 采用 $O(n2^n)$ 或 $O(2^n)$ 应该都可以。 - $e(T\to S-T)$ 直接求时间复杂度难以承受，不过发现固定 $S$ 时是可以利用简单容斥递推计算的（考虑 $T$ 中的一个点 $u$，$e(T\cup\{u\}\to S-(T\cup\{u\}))$ 和 $e(T\to S)$ 的关系即可），所以优化到了 $O(3^n)$。 - $h(S),f(S)$ 只需要直接枚举子集转移即可，时间复杂度 $O(3^n)$。 于是时间复杂度 $O(3^n)$ 可以通过本题，实现并不困难。 [Submission](https://uoj.ac/submission/737288)。