Submission #1364203

---

Source Code Expand

// In the name of God

#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>
#include <complex>

using namespace std;

#define rep(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline bool smin(T &a, const T &b)   { return a > b ? a = b : a;    }
template<typename T> inline bool smax(T &a, const T &b)   { return a < b ? a = b : a;    }

typedef long long LL;

const int N = 1 << 15, mod = (int) 1e9 + 7;
int cnt[N][16], valid[N], dp[N], mask_in[N], out[N], in[N];
int main() {
	valid[0] = valid[3] = 1;
	int n, m;
	cin >> n >> m;
	for (int j = 0; j < m; ++j) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		out[u] |= 1 << v;
		in[v] |= 1 << u;
	}
	for (int mask = 0; mask < (1 << n); ++mask) {
		for (int v = 0; v < n; ++v)
			if (mask >> v & 1)
				mask_in[mask] |= in[v];
		for (int v = 0; v < n; ++v) if (mask >> v & 1)
			for (int u = 0; u < n; ++u)
				if (in[v] & (1 << u))
					cnt[mask][u]++;
		int ways = 1;
		for (int u = 0; u < n; ++u)
			if (~mask >> u & 1)
				ways = (LL) ways * ((1 << cnt[mask][u]) - 1) % mod;
		if (valid[mask & 3] && (mask_in[mask] & (((1 << n) - 1) ^ mask)) == (((1 << n) - 1) ^ mask)) dp[mask] = ways;
	}
	for (int mask = 1; mask < (1 << n); ++mask) {
		for (int sub = (mask - 1) & mask; sub; sub = (sub - 1) & mask) {
			if (valid[sub & 3] && (mask_in[sub] & (((1 << n) - 1) ^ mask)) == (((1 << n) - 1) ^ mask)) {
				int ways = 1;
				for (int j = 0; j < n; ++j)
					if (~sub >> j & 1)
						ways = ((LL) ways * ((1 << cnt[sub][j]) - (~mask >> j & 1))) % mod;
				dp[mask] = (dp[mask] + (LL) ways * dp[sub ^ mask]) % mod;
			}
		}
	}
	int all = 1;
	for (int j = 0; j < m; ++j) all = (all + all) % mod;
	cout << (all - dp[(1 << n) - 1] + mod) % mod << endl;
}

Submission Info

Judge Result