Submission #1775299

---

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;}
inline 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],bit[16];
int q[16][16],deg[16];
void init(ll S){for (int i=0;i<15;i++) a[i]=S&15,S>>=4;}
struct hash_table{
	typedef unsigned long long ull;
	typedef pair<ll,int> pii;
	vector<pii> a;
	void init(int size){
		a.resize(size,pii(-1,0));
	}
	int& operator [] (ll x){
		ull key=x^531515465ll;
		key^=key<<13;
		key^=key>>17;
		key^=key<<5;
		vector<pii>::iterator p=a.begin()+key%a.size();
		while (~p->first&&p->first!=x){
			++p;
			if (p==a.end()) p=a.begin();
		}
		p->first=x;
		return p->second;
	}
}M[20];
//map<ll,int> M[20];
unsigned long long add;int add_cnt=0;
inline void work2(int v){
	register char j;
	static char cnt1[16];
	memset(cnt1,0,16);
	for (j=0;j<deg[n-1];j++) cnt1[a[q[n-1][j]]]++;
	static char cnt2[16];
	memset(cnt2,0,16);
	for (j=0;j<deg[n-2];j++) cnt2[a[q[n-2][j]]]++;
	static char suf[16];
	suf[15]=0;
	for (j=14;j>=0;j--) suf[j]=suf[j+1]+cnt1[j]+cnt2[j];
	for (j=0;v;j++){
		add+=((ll)v<<suf[j+1]);
		add_cnt++;
		if (add_cnt==32) ans=(ans+add)%p,add_cnt=0,add=0;
		v=mul(v,bit[cnt1[j]]*bit[cnt2[j]]);
	}
}
void work1(int v){
	static char cnt[16],suf[16];
	static char i=n-3,j,lim=0;
	memset(cnt,0,16);
	for (j=0;j<i;j++) if (go[i][j]) cnt[a[j]]++;
	for (j=14;j>=0;j--) suf[j]=suf[j+1]+cnt[j];
	while (cnt[lim]) lim++;
	for (int j=0;j<=lim;j++){
		a[i]=j;
		work2(mul(v,1<<suf[j+1]));
		v=mul(v,bit[cnt[j]]);
	}
}
char cnt[20],suf[20];
int main()
{
	//freopen("a.txt","r",stdin);
	for (int i=0;i<16;i++) bit[i]=(1<<i)-1;
	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;
	}
	for (int i=0;i<=9;i++) M[i].init(2e5);
	M[10].init(1e6);
	M[11].init(6e6);
	M[0][0]=1;
	for (int i=0;i<11;i++)
	for (auto pr:M[i].a)
	if (~pr.first){
		register int v=pr.second;
		register ll S=pr.first;
		init(S);
		register char j,lim=0;
		memset(cnt,0,12);
		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 (char 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].a)
		if (~pr.first){
			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].a)
		if (~pr.first) init(pr.first),work1(pr.second);
		ans=(ans+add)%p;
		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:75: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:78: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