Submission #1774890


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],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;}
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 (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 (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];
	register ll add=0;
	for (j=0;v;j++){
		add+=v*(1ll<<(suf1[j+1]+suf2[j+1]));
		v=mul(v,bit[cnt1[j]]*bit[cnt2[j]]);
	}
	inc(ans,add%p);
}
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,bit[cnt[j]]);
	}
}
char cnt[20],suf[20];
int main()
{
	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;
	}
	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

Submission Time
Task F - Games on DAG
User FoolMike
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2250 Byte
Status TLE
Exec Time 5278 ms
Memory 314880 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:52: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:55: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

Set Name Sample All
Score / Max Score 0 / 0 0 / 1600
Status
AC × 4
AC × 34
TLE × 6
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt
Case Name Status Exec Time Memory
0_00.txt AC 1 ms 256 KB
0_01.txt AC 1 ms 256 KB
0_02.txt AC 1 ms 256 KB
0_03.txt AC 1 ms 256 KB
1_00.txt AC 1 ms 256 KB
1_01.txt AC 1 ms 256 KB
1_02.txt AC 1 ms 256 KB
1_03.txt TLE 5277 ms 314880 KB
1_04.txt AC 3635 ms 200832 KB
1_05.txt TLE 5278 ms 314880 KB
1_06.txt AC 806 ms 49664 KB
1_07.txt AC 1669 ms 103040 KB
1_08.txt TLE 5278 ms 314880 KB
1_09.txt AC 2679 ms 153856 KB
1_10.txt AC 3405 ms 209152 KB
1_11.txt AC 2212 ms 124032 KB
1_12.txt AC 4534 ms 239232 KB
1_13.txt AC 3860 ms 213504 KB
1_14.txt TLE 5182 ms 270592 KB
1_15.txt AC 1573 ms 94464 KB
1_16.txt AC 1336 ms 80640 KB
1_17.txt TLE 5275 ms 290944 KB
1_18.txt AC 344 ms 24448 KB
1_19.txt TLE 5271 ms 271232 KB
1_20.txt AC 2 ms 256 KB
1_21.txt AC 137 ms 23680 KB
1_22.txt AC 17 ms 2560 KB
1_23.txt AC 108 ms 9856 KB
1_24.txt AC 2 ms 384 KB
1_25.txt AC 6 ms 1536 KB
1_26.txt AC 562 ms 38784 KB
1_27.txt AC 18 ms 5120 KB
1_28.txt AC 1 ms 256 KB
1_29.txt AC 982 ms 151808 KB
1_30.txt AC 1 ms 256 KB
1_31.txt AC 1775 ms 103808 KB
1_32.txt AC 1067 ms 173824 KB
1_33.txt AC 10 ms 2944 KB
1_34.txt AC 22 ms 4736 KB
1_35.txt AC 400 ms 67072 KB