Submission #2245643

---

Source Code Expand

#include<iostream>
#include<cstdio>
#define mod 1000000007
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int f[1<<15],n,m,ans,b[16],num[1<<15],q[1<<15],top,B[1<<15];
int lb[1<<15],head[1<<15],cnt=0,h[1<<15],g[1<<15];
struct edge{int to,next,w;}e[14349005];
inline void ins(int f,int t,int w){e[++cnt]=(edge){t,head[f],w};head[f]=cnt;}
int main()
{
	n=read();m=read();g[0]=f[0]=h[0]=1;
	for(int i=1;i<=m;++i)
	{
		int x=read(),y=read();
		b[x]|=1<<y-1;B[y]|=1<<x-1;
	}
	for(int i=1;i<1<<n;++i)
	{
		num[i]=num[i>>1]+(i&1);
		for(int j=0;j<n;++j) if(i&(1<<j)) {lb[i]=j;break;}
	}
	for(int i=1;i<1<<n;++i) if((i&3)<3)
	{
		top=0;int r=(1<<n)-1-i;
		for(int j=r;;j=(j-1)&r) if(q[++top]=j,!j) break;
		for(int j=top;j;--j)
		{
			int x=q[j];
			if(x) 
				g[x]=1LL*g[x^(1<<lb[x])]*((1<<num[b[lb[x]+1]&i])-1)%mod,
				h[x]=1LL*h[x^(1<<lb[x])]*(1<<num[B[lb[x]+1]&i])%mod;
			if(g[x]) ins((1<<n)-1-i-x,(1<<n)-1-x,1LL*g[x]*h[x]%mod);
		}
	}
	for(int i=0;i<1<<n;++i) 
	{
		for(int j=head[i];j;j=e[j].next)
			f[e[j].to]=(f[e[j].to]+1LL*f[i]*e[j].w)%mod;	
	}
	printf("%d\n",f[(1<<n)-1]); 
	return 0;
}

Submission Info

Judge Result