Submission #3000901

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<int, P> E;
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	b += MOD;
	a += b;
	a %= MOD;
}

ll dp[66666];
vector<int> g[20];

int main(void){
	int n,m,i,j,k,t,x,y;
	bool used[20],flag;
	fill(dp,dp+66666,0ll);
	cin >> n >> m;
	t = (1<<n);
	for(j=0; j<m; ++j){
		cin >> x >> y;
		--x; --y;
		g[y].push_back(x);
	}
	dp[0] = 1ll;
	for(i=0; i<t; ++i){
		fill(used,used+20,false);
		for(j=0; j<n; ++j){
			if(i&(1<<j)){
				used[j] = true;
			}
		}
		for(j=0; j<n; ++j){
			if(used[j]){
				continue;
			}
			flag = true;
			for(k=(g[j].l_ength()-1); k>=0; --k){
				if(!used[g[j][k]]){
					flag = false;
					break;
				}
			}
			if(flag){
				dp[i+(1<<j)] += dp[i];
			}
		}
	}
	cout << (dp[t-1]) << endl;
	return 0;
}

Submission Info

Judge Result