Submission #1774856

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p=1e9+7;
inline void inc(int &x,int y){x+=y;if (x>=p) x-=p;}
int mul(int x,int y){return (ll)x*y%p;}
int power(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=mul(x,x))
		if (y&1) ans=mul(ans,x);
	return ans;
}
int n,m,ans,go[20][20],a[16];
int q[16][16],deg[16];
void init(ll S){for (int i=0;i<15;i++) a[i]=S&15,S>>=4;}
map<ll,int> M[20];
void work2(int v){
	register char j;
	register char cnt1[16],suf1[16];
	memset(cnt1,0,16);suf1[15]=0;
	//for (int j=0;j<n-2;j++) if (go[n-1][j]) cnt1[a[j]]++;
	for (j=0;j<deg[n-1];j++) cnt1[a[q[n-1][j]]]++;
	for (j=14;j>=0;j--) suf1[j]=suf1[j+1]+cnt1[j];
	register char cnt2[16],suf2[16];
	memset(cnt2,0,16);suf2[15]=0;
	//for (int j=0;j<n-2;j++) if (go[n-2][j]) cnt2[a[j]]++;
	for (j=0;j<deg[n-2];j++) cnt2[a[q[n-2][j]]]++;
	for (j=14;j>=0;j--) suf2[j]=suf2[j+1]+cnt2[j];
	for (j=0;v;j++){
		inc(ans,mul(v,1<<(suf1[j+1]+suf2[j+1])));
		v=mul(v,((1<<cnt1[j])-1)*((1<<cnt2[j])-1));
	}
}
void work1(int v){
	static int cnt[20],suf[20];
	int i=n-3;
	for (int j=0;j<15;j++) cnt[j]=0;
	for (int j=0;j<i;j++) if (go[i][j]) cnt[a[j]]++;
	for (int j=15;j>=0;j--) suf[j]=suf[j+1]+cnt[j];
	int lim=0;
	while (cnt[lim]) lim++;
	for (int j=0;j<=lim;j++){
		a[i]=j;
		work2(mul(v,1<<suf[j+1]));
		v=mul(v,(1<<cnt[j])-1);
	}
}
char cnt[20],suf[20];
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		u=n-u;v=n-v;
		go[u][v]=1;
		if (v!=n-2) q[u][deg[u]++]=v;
	}
	M[0][0]=1;
	for (int i=0;i<11;i++)
	for (auto pr:M[i]){
		register int v=pr.second;
		register ll S=pr.first;
		init(S);
		register char j,lim=0;
		for (j=0;j<12;j++) cnt[j]=0;
		for (j=0;j<=i;j++) if (go[i+1][j]) cnt[a[j]]++;
		for (j=11;j>=0;j--) suf[j]=suf[j+1]+cnt[j];
		while (cnt[lim]) lim++;
		for (int j=0,bit=(i+1)<<2;j<=lim;j++){
			inc(M[i+1][(ll)j<<bit|S],mul(v,1<<suf[j+1]));
			v=mul(v,(1<<cnt[j])-1);
		}
	}
	if (n<=12){
		for (auto pr:M[n-1]){
			int v=pr.second;ll S=pr.first;
			init(S);
			if (a[n-1]!=a[n-2]) inc(ans,v);
		}
		printf("%d\n",ans);
	}
	else{
		for (auto pr:M[n-4]) init(pr.first),work1(pr.second);
		ans=(power(2,m)+p-ans)%p;
		printf("%d\n",ans);
	}
	return 0;
}

Submission Info

Compile Error

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

Judge Result