题目

这可算是一道非常好的关于容斥原理的题了。

算法

好吧，这题我毫无思路，直接给正解。

首先，问题的正面不容易求，那么就求反面吧：

有多少种添加边的方案，使得这个图是DAG图（这里及以下所说的DAG图都是指这个图不是整个强连通的）。

利用容斥原理，DAG图的特征是有至少一个入度为\(0\)的点并且这个图不止一个点（这里及以下所说的点都是指求强连通后的点），就根据这个进行容斥。

设\(g(set)\)为集合里的点都是入度为\(0\)的方案数，注意，这个有点特别，比如这个：

它的值应该为\(0\)。虽然有两种方案，一种是两条边都添加，另一种是都不添加。但是，都不添加的话，由于两个点（偶数个点），系数应该是负的！！所以\(g(set) = (-1) + (1) = 0\)。

设\(f(set)\)为有多少种添加边的方案，使得整个图强连通。

好吧，我真的不知道怎样说清楚。-_-|||。不过看了代码应该就很清楚了。。。

这里的\(h(set)\)是这些点的诱导子图有多少条边。

至于时间复杂度，就是$$O(\sum_{i=0}^{n}{Ci_n\cdot 2^i})$$

根据二次项定理可知时间复杂度为\(O(3^n)\)。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <assert.h>

using namespace std;

#ifdef debug

#define ep(...) fprintf(stderr, __VA_ARGS__)

#else

#define ep(...) assert(true)

#endif 

	template <class T>

void relax(T &a, const T &b)

{

	if (b > a) a = b;

}

	template <class T>

void tension(T &a, const T &b)

{

	if (b < a) a = b;

}

typedef long long i64;

const int MaxN = 15;

const int MaxSet = (1 << MaxN) + 3;

const int MOD = (int) 1e9 + 7;

int main()

{

#if defined(debug) || defined(local)

	freopen("in", "r", stdin);

	freopen("out", "w", stdout);

#endif

	int n, m;

	scanf("%d%d", &n, &m);

	static int in[MaxSet], out[MaxSet];

	for (int i = 0; i < m; i ++)

	{

		int u, v;

		scanf("%d%d", &u, &v);

		u --, v --;

		in[1 << v] |= 1 << u;

		out[1 << u] |= 1 << v;

	}

	static int cnt[MaxSet], power2[MaxSet];

	power2[0] = 1;

	for (int i = 1; i < 1 << n; i ++)

	{

		cnt[i] = cnt[i ^ (i & -i)] + 1;

		power2[i] = power2[i - 1] << 1;

		if (power2[i] >= MOD) power2[i] -= MOD;

	}

	static int f[MaxSet], g[MaxSet], h[MaxSet];

	for (int i = 1; i < 1 << n; i ++)

	{

		if (cnt[i] == 1)

		{

			f[i] = g[i] = 1;

			h[i] = 0;

			continue;

		}

		int u = i & -i;

		h[i] = h[i ^ u] + cnt[out[u] & i] + cnt[in[u] & i];

		for (int sub = (i - 1) & i; sub; sub = (sub - 1) & i)

			if (sub & u)

			{

				g[i] = ((i64) g[i] + MOD - (i64) g[i ^ sub] * f[sub]) % MOD;

			}

		static int w[MaxSet];

		int rev_f = 0;

		for (int sub = i; sub; sub = (sub - 1) & i)

		{

			if (sub == i)

			{

				w[sub] = 0;

			}

			else

			{

				int v = (i ^ sub) & -(i ^ sub);

				w[sub] = w[sub ^ v] - cnt[out[v] & (i ^ sub)] + cnt[in[v] & sub];

			}

			rev_f = ((i64) rev_f + (i64) g[sub] * power2[h[i ^ sub] + w[sub]]) % MOD;

		}

		f[i] = (power2[h[i]] + MOD - rev_f) % MOD;

		ep("tmp_g: %d\n", g[i]);

		g[i] = (g[i] + f[i]) % MOD;

		ep("%d: %d %d %d\n", i, f[i], g[i], h[i]);

	}

	cout << f[(1 << n) - 1] << endl;

	ep("answer %d", f[(1 << n) - 1]);

	return 0;

}