Submission #1365507

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <functional>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <string>
#define SIZE 20
#define BT 1<<16
#define MOD 1000000007

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

ll dp[BT],rt[SIZE];
ll nxt[BT],memo[SIZE][SIZE];
ll cnt[SIZE][BT];
ll nt[BT];
bool use[SIZE][SIZE];


int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=0;i<m;i++)
	{
		int x,y;
		scanf("%d %d",&x,&y);x--,y--;
		use[x][y]=true;
	}
	for(int i=0;i<n;i++)
	{
		for(int S=0;S<1<<n;S++)
		{
			cnt[i][S]=0;
			for(int j=0;j<n;j++)
			{
				if(use[i][j]&&(S>>j&1))
				{
					cnt[i][S]=(cnt[i][S]*2LL+1)%MOD;
				}
			}
		}
	}
	for(int S=0;S<1<<n;S++)
	{
		nt[S]=1;
		for(int i=0;i<n;i++)
		{
			if(S>>i&1)
			{
				for(int j=i+1;j<n;j++)
				{
					if(S>>j&1)
					{
						if(use[i][j]) nt[S]=nt[S]*2LL%MOD;
					}
				}
			}
		}
	}
	memset(dp,0,sizeof(dp));
	dp[0]=1;
	ll ret=0;
	for(int i=0;i<n;i++)
	{
		memset(nxt,0,sizeof(nxt));
		for(int S=0;S<1<<n;S++)
		{
			if(dp[S]==0) continue;
			int T=(1<<n)-S-1;
			for(int K=T;K>0;K=T&(K-1))
			{
				int zan=T-K;
				ll way=dp[S];
				for(int j=0;j<n;j++)
				{
					if(zan>>j&1)
					{
						way=way*cnt[j][K]%MOD;
					}
					else if(K>>j&1)
					{
						way=way*(cnt[j][zan]+1)%MOD;
					}
				}
				nxt[S+K]+=way;
				if(nxt[S+K]>=MOD) nxt[S+K]>=MOD;
				if((K>>0&1)&&(K>>1&1))
				{
					ret+=way*nt[zan]%MOD;
					if(ret>=MOD) ret-=MOD;
				}
			}
		}
		for(int S=0;S<1<<n;S++) dp[S]=nxt[S];
	}
	ll all=1;
	for(int i=0;i<m;i++) all=all*2LL%MOD;
	printf("%lld\n",(all-ret+MOD)%MOD);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:30:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
./Main.cpp:34:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);x--,y--;
                       ^

Judge Result