Submission #1611915

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <cassert>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int dp[(1<<15)+5][16],n,m;
int c[15][(1<<15)],u[15][15];
ll *zip[(1<<15)];
int main(){
	cin>>n>>m;
	rep(i,m){
		int a,b;cin>>a>>b;
		a--; b--;
		u[a][b] = 1;
	}
	rep(i,n)rep(j,(1<<n)){
		if(((j>>i)&1)) continue;
		rep(k,n){
			if(((j>>k)&1)) if(u[i][k]) c[i][j]++;
		}
	}
	//cout<<c[0][2]<<" " <<c[1][1]<<endl;
	dp[0][0] = 1; ll ret=0;
	rep(i,(1<<n)) zip[i] = new ll[(1<<__builtin_popcount(i))];
	for(int t=0;t<n;t++){
		for(int mask=0;mask<(1<<n);mask++){
			int x = mask,num = 0;
			while(1){
				//dp[x][t] -> dp[mask][t+1]
				int y = mask-x,z = (1<<n)-1-mask;
				ll val = 1;
				if(!t){
	    				rep(i,n){
	    					if(((x>>i)&1)){
	    						val = val*(1LL<<c[i][y])%mod;
	    					}
	    					else if(((z>>i)&1)){
	    						val = val*((1LL<<c[i][y])-1LL)%mod;
	    					}
	    				}
	    				zip[mask][num++] = val;
				}else val = zip[mask][num++];
				
				if(y%4 != 3){
				    dp[mask][t+1] = dp[mask][t+1]+dp[x][t]*val%mod;
				    dp[mask][t+1]%=mod;
				    if(mask == (1<<n)-1 && y) ret+=dp[x][t]*val%mod;
				}
				if(x == 0) break;
				x = (x-1)&mask;
				//cout<<x<<" " <<mask<<endl;
			}
		}
	}
	cout<<ret%mod<<endl;
}

Submission Info

Judge Result