UOJ37 主旋律

有点（？）难推的容斥 + 状态压缩。

题意：问 $n$ 个点 $m$ 条边的有向图中，任意保留一些边使得 $n$ 个点仍然是一个强连通分量的方案数。$n\leq 15, m\leq n(n - 1)$。

定义 $f(s)$ 表示集合 $s$ 中所有点及内部的边（指端点都属于 $s$）任意保留使得仍然是强连通分量的方案数。

首先设 $E(s_1, s_2)$ 表示起点在 $s_1$ 集合中，终点在 $s_2$ 集合中的边数。

显然正着不好做，考虑容斥，那么不止一个强连通分量，那么缩点后一定会产生出度为 0 的点，钦定强连通分量出度为 0 的点集合为 $t_1$，没被选中的集合为 $t_2$，那么 $E(t_2, t_1)$ 和 $E(t_2, t_2)$ 都是可以选的，$E(t_1, t_1)$ 的贡献由 $g(t_1)$ 计算，那么可以得到：

$$g(s) = 2 ^ {E(s, s)} - \sum_{t_1 \subsetneq s} 2 ^ {E(t_2, t_1) + E(t_2, t_2)} g(t_1)$$

注意此时我们的 $g(s)$ 是自带系数的，根据经典的容斥，我们 $g(s)$ 的系数应该是 $(-1) ^ {k + 1}$，$k$ 表示出度为 0 的点的强连通分量个数。

然后考虑 $g(s)$ 的定义式，我们枚举最小编号所在的集合，那么就可以得到：

$$g(s) = -\sum_{t\subsetneq s, t\not=\varnothing}[id\in t]f(t)g(s/t) + f(s)$$

前面我们可以计算到 $g(s)$，把这个式子变一下形，可以得到：

$$f(s) = g(s) + \sum_{t\subsetneq s, t\not= \varnothing}[id\in t]f(t)g(s/t)$$

即可做到 $O(3 ^ n)$ 计算，可以通过。代码中是将 $g(0)$ 设为 -1，贡献不变。

两个集合之间的连边可以枚举一边集合的点，计算另一边到这个点的边数，到点的边数可以预处理。

int main()
{
	int m;
	std::cin >> n >> m;
	pw2[0] = 1;
	for (int i = 1; i < M; ++ i) adj(pw2[i] = (pw2[i - 1] << 1) - Mod);
	for (int i = 1, u, v; i <= m; ++ i)
		std::cin >> u >> v, edg[-- u][-- v] ++;
	for (int s = 1; s < (1 << n); ++ s)
		for (int u = 0; u < n; ++ u)
			for (int v = 0; v < n; ++ v)
				if ((s >> u & 1) && (s >> v & 1)) in[s] += edg[u][v];
	for (int s = 1; s < (1 << n); ++ s)
		for (int u = 0; u < n; ++ u)
			for (int v = 0; v < n; ++ v)
				if (s >> v & 1) to[s][u] += edg[v][u];
	g[0] = Mod - 1;
	auto calclink = [&](int s1, int s2) {
		int res = 0;
		while (s2) res += to[s1][ctz(s2)], s2 ^= s2 & -s2;
		return res;
	};
	for (int s = 1; s < (1 << n); ++ s)
	{
		g[s] = pw2[in[s]];
		for (int frm = s & (s - 1); frm; frm = (frm - 1) & s)
			adj(g[s] -= (LL) g[frm] * pw2[in[s ^ frm]] % Mod * pw2[calclink(s ^ frm, frm)] % Mod);
	}
	for (int s = 1; s < (1 << n); ++ s)
	{
		f[s] = g[s];
		int le = ctz(s);
		for (int frm = s & (s - 1); frm; frm = (frm - 1) & s)
			if (frm >> le & 1) f[s] = (f[s] + (LL) f[frm] * g[s ^ frm]) % Mod;
	}
	std::cout << f[(1 << n) - 1] << std::endl;
	return 0;
}