BZOJ-3812. 主旋律

题目给出一个 $n$ 个点，$m$ 条边的有向图，要求求出删掉一些边以后，整个图强联通的方案数，其中 $n \leq 15, m \leq n(n-1)$

样例是这样的，十分良心，一共有 $9390$ 种方案

题目链接：BZOJ-3812

这是陈老师的神题，一直纠结了我三四天才会做（你可以在他 WC2015 讲课的 PPT 上找到这题的题解）

首先看到数据范围很容易想到的是可能可以利用子集 DP 来解决问题，题目要求强连通子图的个数，直接求似乎不太容易，可以考虑用子图的个数扣掉不强连通的子图个数，这样就是答案

那么不强联通的子图一定是由很多很多强连通分量组成，我们假设将所有强连通分量缩成点，就会得到一个 DAG，因此一个想法就是枚举强联通分量，然后计算这些强连通分量构成 DAG 的方案数

那么现在考虑一个子问题：一些点构成 DAG 的方案数。一个 DAG 肯定是由一些没有出度的点组成的，我们可以枚举这些点组成的集合 $T$，那么 $V - T$ 内的边和 $V - T$ 到 $T$ 的边随便要不要都是可以的，但是这样有可能会出现重复的情况，因为在枚举 $T$ 的时候这样计算不能保证 $V - T$ 内没有不存在出度的点，也就是说两个点 $u, v$，$T = {u}$ 时会计算一次没有出度的点是 ${u, v}$ 的情况，$T = {v}$ 时也会计算一次，因此需要用容斥原理

设 $f(S)$ 表示点集 $S$ 构成的 DAG 的方案数，那么可以得到转移

\[f(S) = \sum_{T \subseteq S, T \neq \emptyset} (-1)^{|T| - 1} \cdot 2^{ways(S - T, T)} \cdot f(S - T)\]

这里 $ways(S - T, T)$ 表示 $S - T$ 到 $T$ 的边数

然后这样由于要枚举强连通分量，复杂度十分高，这题肯定没办法过

换个角度可以想枚举所有没有出度的强连通分量缩成的点的集合 $T$，根据上面的容斥，如果 $T$ 内的点组成奇数个强连通分量，那么对答案的贡献将是 $1$，如果是偶数个那就是 $-1$

所以用 $g(S)$ 表示将 $S$ 分成若干个强连通分量的方案数，并且算上刚刚说的正负，再用 $f(S)$ 表示 $S$ 的强连通子图的个数（也就是题目要求的东西）

这样的话可以枚举 $T \subset S$，表示 $T$ 单独构成一个强连通分量，然后更新 $g(S)$，为了避免重复统计，找一个点 $u$ 让 $T$ 始终包含 $u$，也就是

\[g(S) = f(S) - \sum_{T \subset S, u \in T} f(T)g(S - T)\]

这里是减去后面的那个卷积是因为多了一个强连通分量对答案的贡献就变成原来的相反数了

这样的话 $f(S)$ 的计算就可以枚举 $T$ 集合，由于容斥已经在 $g(T)$  中一起计算了，所以 $S - T$ 就可以任意划分没有限制，因此

\[f(S) = 2^{h(S)} - \sum_{T \subseteq S, T \neq \emptyset} 2^{ways(S - T, T) + h(S - T)}g(T)\]

这里的 $h(S)$ 表示 $S$ 中边的数量，并且这里的 $g(T)$ 当 $T = S$ 的时候不包含 $f(S)$ 这部分

剩下关于 $ways$ 和 $h$ 的计算可以在计算 $f$ 的时候顺便计算，这样就可以在 $\mathcal O(3^n)$ 时间内计算出答案了

#include <cstdio>

const int MaxN = 15;
const long long mod_v = 1000000007;
long long pw[MaxN * MaxN];
int bitcnt[1 << MaxN], edge_in[1 << MaxN], edge_out[1 << MaxN];
long long f[1 << MaxN], g[1 << MaxN], h[1 << MaxN], p[1 << MaxN];

int main()
{
	int n, m;
	std::scanf("%d %d", &n, &m);
	for(int i = 0; i != m; ++i)
	{
		int u, v;
		std::scanf("%d %d", &u, &v);
		u = 1 << (u - 1), v = 1 << (v - 1);
		edge_out[u] |= v;
		edge_in[v] |= u;
	}

	pw[0] = 1;
	for(int i = 1; i != n * n; ++i)
		pw[i] = (pw[i - 1] << 1) % mod_v;

	bitcnt[0] = 0;
	for(int i = 1; i != 1 << n; ++i)
		bitcnt[i] = bitcnt[i - (i & -i)] + 1;

	for(int s = 1; s != 1 << n; ++s)
	{
		int one = s & -s, outside = s ^ one;
		for(int i = outside; i; i = (i - 1) & outside)
			g[s] = (g[s] - f[s ^ i] * g[i]) % mod_v;

		h[s] = h[outside] 
			+ bitcnt[edge_in[one] & outside]
			+ bitcnt[edge_out[one] & outside];

		f[s] = pw[h[s]];
		for(int i = s; i; i = (i - 1) & s)
		{
			if(i != s)
			{
				int one = (i ^ s) & -(i ^ s);
				p[i] = p[i ^ one] 
					+ bitcnt[edge_out[one] & i]
					- bitcnt[edge_in[one] & (i ^ s)];
			} else p[i] = 0;
			f[s] = (f[s] - pw[h[s ^ i] + p[i]] * g[i]) % mod_v;
		}

		g[s] = (g[s] + f[s]) % mod_v;
	}

	long long ans = (f[(1 << n) - 1] + mod_v) % mod_v;
	std::printf("%lld", ans);

	return 0;
}