Submission #2163084

---

Source Code Expand

#include <bits/stdc++.h>

typedef long long LL;

#define FOR(i, a, b) for (int i = (a), i##_END_ = (b); i <= i##_END_; i++)
#define DNF(i, a, b) for (int i = (a), i##_END_ = (b); i >= i##_END_; i--)

template <typename Tp> void in(Tp &x) {
	char ch = getchar(), f = 1; x = 0;
	while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
	if (ch == '-') ch = getchar(), f = -1;
	while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
	x *= f;
}

template <typename Tp> void out(Tp x) {
	if (x > 9) out(x / 10);
	putchar(x % 10 + '0');
	return;
}

template <typename Tp> Tp Max(const Tp &x, const Tp &y) {return x > y ? x : y;}
template <typename Tp> Tp Min(const Tp &x, const Tp &y) {return x < y ? x : y;}
template <typename Tp> bool chkmax(Tp &x, Tp y) {return x >= y ? 0 : (x=y, 1);}
template <typename Tp> bool chkmin(Tp &x, Tp y) {return x <= y ? 0 : (x=y, 1);}

const int MAXN = 16;
const int MOD = 1000000007;

int n, m;
bool edge[MAXN][MAXN];

int In[MAXN][32768], Out[MAXN][32768];
int f[32768];

int power(int x, int y)
{
	int ret = 1;
	while (y) {
		if (y & 1) ret = 1ll * ret * x % MOD;
		x = 1ll * x * x % MOD;
		y >>= 1;
	}
	return ret;
}

int main()
{
	in(n); in(m);
	FOR(i, 1, m) {int x, y; in(x); in(y); edge[x][y] = true;}

	FOR(i, 1, n) FOR(j, 0, (1 << n) - 1) {
		FOR(k, 1, n) if (j >> (k - 1) & 1) In[i][j] += edge[k][i];
		FOR(k, 1, n) if (j >> (k - 1) & 1) Out[i][j] += edge[i][k];
	}

	f[0] = 1;
	
	FOR(i, 1, (1 << n) - 1) {
		f[i] = 0;
		for (int j = i; j; j = (j - 1) & i) {
			int ret = 1;
			if ((j & 1) ^ (j >> 1 & 1)) continue;
			FOR(k, 1, n) if (j >> (k - 1) & 1) ret = ret * 1ll * power(2, Out[k][i - j]) % MOD;
			FOR(k, 1, n) if ((i - j) >> (k - 1) & 1) ret = ret * 1ll * (power(2, Out[k][j]) - 1) % MOD;
			f[i] = (f[i] + ret * 1ll * f[i - j]) % MOD;
		}
	}

	printf("%d\n", (power(2, m) - f[(1 << n) - 1] + MOD) % MOD);

	return 0;
}

Submission Info

Judge Result