Submission #1775241
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;}
map<ll,int> M[20];
unsigned long long add;int add_cnt=0;
inline void work2(int v){
register char j;
register char cnt1[16];
memset(cnt1,0,16);
for (j=0;j<deg[n-1];j++) cnt1[a[q[n-1][j]]]++;
register char cnt2[16];
memset(cnt2,0,16);
for (j=0;j<deg[n-2];j++) cnt2[a[q[n-2][j]]]++;
register 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];
register 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;
}
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;
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]){
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=(ans+add)%p;
ans=(power(2,m)+p-ans)%p;
printf("%d\n",ans);
}
return 0;
}
Submission Info
Submission Time
2017-11-15 20:50:33+0900
Task
F - Games on DAG
User
FoolMike
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
2298 Byte
Status
MLE
Exec Time
4959 ms
Memory
314880 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:54: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:57: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
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
MLE
4959 ms
314880 KB
1_04.txt
AC
2878 ms
200832 KB
1_05.txt
MLE
4936 ms
314880 KB
1_06.txt
AC
648 ms
49664 KB
1_07.txt
AC
1337 ms
103040 KB
1_08.txt
MLE
4905 ms
314880 KB
1_09.txt
AC
2120 ms
153856 KB
1_10.txt
AC
2737 ms
209152 KB
1_11.txt
AC
1745 ms
124032 KB
1_12.txt
AC
3595 ms
239232 KB
1_13.txt
AC
3051 ms
213504 KB
1_14.txt
MLE
4114 ms
268544 KB
1_15.txt
AC
1253 ms
96512 KB
1_16.txt
AC
1060 ms
80640 KB
1_17.txt
MLE
4417 ms
288896 KB
1_18.txt
AC
263 ms
24448 KB
1_19.txt
MLE
4187 ms
273280 KB
1_20.txt
AC
2 ms
256 KB
1_21.txt
AC
126 ms
23680 KB
1_22.txt
AC
14 ms
2560 KB
1_23.txt
AC
84 ms
9856 KB
1_24.txt
AC
2 ms
384 KB
1_25.txt
AC
5 ms
1536 KB
1_26.txt
AC
432 ms
38784 KB
1_27.txt
AC
16 ms
5120 KB
1_28.txt
AC
1 ms
256 KB
1_29.txt
AC
823 ms
151808 KB
1_30.txt
AC
1 ms
256 KB
1_31.txt
AC
1387 ms
103808 KB
1_32.txt
AC
907 ms
173824 KB
1_33.txt
AC
9 ms
2944 KB
1_34.txt
AC
17 ms
4736 KB
1_35.txt
AC
333 ms
67072 KB