Submission #5943702

---

Source Code Expand

// start fold
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cstring>
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
using namespace std;
#define ri register int
#define il inline
#define LL long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define enter putchar('\n')
#define size(x) ((int)x.size())
#define mem0(x) memset(x,0,sizeof(x))
template<class T>il void in(T &x)
{
	x=0; short f=1; char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') x=x*10+(c^'0'),c=getchar();
	x*=f;
}
template <typename T,typename ...Args>il void in(T &x, Args &...args)
{
	in(x); in(args...);
}
template<class T>il void out(T x,const char c='\n')
{
	static short st[30];
	short m=0;
	if(x<0) putchar('-'),x=-x;
	do st[++m]=x%10,x/=10; while(x);
	while(m) putchar(st[m--]|'0');
	putchar(c);
}
template <typename T,typename ...Args>il void out(const T &x,const Args &...args)
{
	out(x,' '); out(args...);
}
template<class T>il void print(T a[],int n)
{
	if(n<=0) return;
	for(ri i=0; i<n; ++i) out(a[i],' ');
	enter;
}
namespace i207M
{
// end fold
#define N 16
#define M N*N
const int md=1e9+7;
int n,m;
int v[M],nx[M],head[N],cnte=1;
il void adde(const int uu,const int vv)
{
	v[++cnte]=vv,nx[cnte]=head[uu],head[uu]=cnte;
}
int ined[1<<N];
int f[2][1<<N];
int pw2[M];
int bit,ys[1<<N];
signed main()
{
#ifdef M207
	freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
#endif
	in(n,m); pw2[0]=1; bit=(1<<n)-1;
	for(ri i=0; i<n; ++i) ys[1<<i]=i;
	for(ri i=1,a,b; i<=m; ++i)
	{
		in(a,b); --a,--b;
		adde(a,b), adde(b,a);
		pw2[i]=(pw2[i-1]<<1)%md;
	}
	for(ri s=1; s<=bit; ++s)
	{
		int x=s&-s;
		ined[s]=ined[s^x],x=ys[x];
		for(ri i=head[x]; i; i=nx[i])
			if((s>>v[i])&1) ++ined[s];
	}
	for(ri c=0; c<=1; ++c)
		for(ri s=1; s<=bit; ++s)
			if((s>>c)&1)
			{
				int val=pw2[ined[s]];
				for(ri t=s&(s-1); t; t=s&(t-1))
					if((t>>c)&1)
					{
						val=(val-(LL)f[c][t]*pw2[ined[s^t]]%md+md)%md;
					}
				f[c][s]=val;
			}
	int ans=0;
	for(ri s=1; s<=bit; ++s)
		if(s&1)
		{
			int bu=bit^s;
			for(ri t=bu; t; t=bu&(t-1))
				if((t&2)&&ined[s]+ined[t]==ined[s|t])
					ans=(ans+(LL)f[0][s]*f[1][t]%md*pw2[ined[(s|t)^bit]])%md;
		}
	ans=(pw2[m]-ans+md)%md;
	out(ans);
	return 0;
}
// start fold
}
signed main()
{
	i207M::main();
	return 0;
}
// end fold

Submission Info

Judge Result