UOJ-37 清华集训2014 主旋律

Description

给定一场 \(n\) 个点，\(m\) 条边的有向图，你可以删去一些边，要求剩下的吐仍然强连通。求方案数 \(\bmod (10^9+7)\) 的值。

Hint

\(1\le n\le 15, 0\le m\le n(n-1)\)

Solution

orz 神仙容斥

首先，根据正难则反的思路，合法方案数等于，总方案数 \(2^m\) 减去不合法方案数。不合法，即将图进行 SCC 缩点之后并不是一个点而是一个 DAG。那么分为两部分：DAG，以及其中的 SCC。

首先定义 \(D(S)\) 为点集 \(S\) 构成的诱导子图中，为 DAG 的生成子图个数。那么构造这个 DAG 是思路是，选定一个点集 \(T\)，作为没有入度的点，从 \(T\) 向 \(S \backslash T\) 任意连边。那么一个 naive 思想是（\(E(V_1,V_2)\) 表示出点在 \(V_1\) 入点在 \(V_2\) 的边的数量）：

但这样会算重，比如 \(2\to 1, 3\to 1\) 这张图，会在计算 \(S=\{1, 2, 3\}\)，枚举子集 \(T=\{2\}, \{3\},\{2, 3\}\) 都会被算一遍。那么用容斥原理解决：

然后思考怎么算 SCC。首先定义一个 \(F(S)\) 表示点集 \(S\) 构成的诱导子图中，为强连通图的生成子图个数（即答案，\(F(\{1, 2, \cdots,n\})\) 即为所求）。

接下来引入两个记号（没错都是从这里贺的）：

• \(\text{PA}(S:\{T\}_{i=1}^k)\) 表示枚举将 \(S\) 拆分为 \(T_1, T_2, \cdots, T_k\) 的所有方案，所谓拆分即满足 \(\cup_{i=1}^k T_i=S\) 切对于任意的 \(i, j\in[1, k]\)，\(T_i, T_j\) 不交。
• \(\text{SPA}(S:\{T\}_{i=1}^k)\) 表示枚举 \(S\) 的严格拆分，即强制要求 \(k\ge 2\)。

那么可以列出 \(F\) 的公式（\(E(S)\) 表示出入点都在 \(S\) 中的边数，即 \(E(S, S)\)）：

注意，上面 \(D\) 的定义虽然是针对点集的，但 \(T\) 在此应为“点集的点集”，此处可能不够严谨，不妨简单视为 \(T\) 中的元素本身是缩点后的点，\(D(T)\) 则是用这些缩完后的点间的边（原图 SCC 之间的边）构成 DAG。然后把 \(D(T)\) 展开，得：

这个式子丝毫的不可做，但我们仔细观察这两个 \(\Sigma\)，是枚举划分再枚举子集。然而我们反过来，先枚举子集，在枚举子集的划分，是完全等价的。那么魔改一下上面的式子：

考虑把 \((-1)^{k+1}\prod_{i=1}^k F(U_i)\) 提到第二个 \(\Sigma\) 后，发现这样其实可以使 \(U,V\) 两部分分开。设 \(G(S)=\sum\limits_{\text{PA}(S:\{T\}_{i=1}^k)} (-1)^{k+1} \prod_{i=1}^k F(T_i)\)。

带入原式子得：

把 \(2^{E(T, S\backslash T)}\) 放后面是为什么呢？仔细观察这个 \(\sum\limits_{\text{PA}((S\backslash T):\{V\}_{i=1}^l)}D (V)\prod _{i=1}^l F(V_i)\)，发现是枚举了 DAG 再将缩掉的点拆开。这相当于什么？是不是任意图？果断换掉这个鸡肋玩意，这样拆分就不用了：

考虑将 \(G\) 写成可以直接 dp 的式子，避开 \(\text{PA}\)，即得：

其中 \(u\) 是任取的，在求和过程中固定这么一个 \(u\) 是为什么呢？首先要知道在没有 \(u\in T\) 时会算重，具体的，对于一张图，有一个 SCC 的点集为 \(U\)，在 \(T=U\) 时在 \(F(T)\) 被算了一次，而 \(U\subseteq S\backslash T\) 时又可能在 \(G(S\backslash T)\) 中被算一遍。

为什么 \(u\in T\) 开始让我们不重？考虑两张图相同，必要条件是 \(u\) 所在 SCC 的编号相同。但这样保证了编号不同，自然就不重了。如果这是正确的，还得保证不漏。首先 \(u\) 所在 SCC 会被枚举到，而其他部分在 \(G(S\backslash T)\) 已经确定是可以的了。

最后 \(F,G\) 一起 dp 就行了，复杂度最优秀可以 \(O(3^n)\)。然而一次 \(O(n)\) 计算 \(E\) 也是可以过的，复杂度 \(O(3^n n)\)。

Code

/*
 * Author : _Wallace_
 * Source : https://www.cnblogs.com/-Wallace-/
 * Problem : UOJ 37 清华集训2014 主旋律
 */
#include <iostream>

const int N = 15;
const int mod = 1e9 + 7;
typedef long long ll;

inline int& adjust(int& x) {
	if (x < 0) return x += mod;
	if (x >= mod) return x -= mod;
	return x;
}

int n, m, adj[N];
int f[1 << N], g[1 << N];
int pw2[N * N];
int popc[1 << N], rank[1 << N];

inline int edges(int s, int t) {
	int ret = 0;
	for (; s; s -= s & -s)
		ret += popc[adj[rank[s & -s]] & t];
	return ret;
}
inline int edges(int s) {
	return edges(s, s);
}

signed main() {
	std::cin >> n >> m;
	for (int i = 1, u, v; i <= m; i++) {
		std::cin >> u >> v;
		adj[u - 1] |= (1 << (v - 1));
	}

	popc[0] = 0;
	for (int s = 1; s < (1 << n); s++)
		popc[s] = popc[s >> 1] + (s & 1);
	for (int i = 0; i < n; i++)
		rank[1 << i] = i;

	pw2[0] = 1ll;
	for (int i = 1; i < N * N; i++)
		pw2[i] = pw2[i - 1] * 2ll % mod;

	for (int s = 1; s < (1 << n); s++) {
		if (popc[s] == 1) { f[s] = g[s] = 1; continue; }
		int fix = s & -s, rem = s ^ fix;
		for (int t = rem; ; t = (t - 1) & rem) {
			adjust(g[s] = g[s] - (ll)f[(t | fix)] * g[s ^ (t | fix)] % mod);
			if (!t) break;
		}
		for (int t = s; t; t = (t - 1) & s)
			adjust(f[s] += (ll)g[t] * pw2[edges(s ^ t)] % mod * pw2[edges(s ^ t, t)] % mod);
		adjust(f[s] = (pw2[edges(s)] - f[s] + mod));
		adjust(g[s] = (g[s] + f[s]));
	}
	printf("%d\n", f[(1 << n) - 1]);
	return 0;
}

UOJ-37 清华集训2014 主旋律

原文：https://www.cnblogs.com/-Wallace-/p/uoj37.html