Submission #2245643
Source Code Expand
#include<iostream> #include<cstdio> #define mod 1000000007 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int f[1<<15],n,m,ans,b[16],num[1<<15],q[1<<15],top,B[1<<15]; int lb[1<<15],head[1<<15],cnt=0,h[1<<15],g[1<<15]; struct edge{int to,next,w;}e[14349005]; inline void ins(int f,int t,int w){e[++cnt]=(edge){t,head[f],w};head[f]=cnt;} int main() { n=read();m=read();g[0]=f[0]=h[0]=1; for(int i=1;i<=m;++i) { int x=read(),y=read(); b[x]|=1<<y-1;B[y]|=1<<x-1; } for(int i=1;i<1<<n;++i) { num[i]=num[i>>1]+(i&1); for(int j=0;j<n;++j) if(i&(1<<j)) {lb[i]=j;break;} } for(int i=1;i<1<<n;++i) if((i&3)<3) { top=0;int r=(1<<n)-1-i; for(int j=r;;j=(j-1)&r) if(q[++top]=j,!j) break; for(int j=top;j;--j) { int x=q[j]; if(x) g[x]=1LL*g[x^(1<<lb[x])]*((1<<num[b[lb[x]+1]&i])-1)%mod, h[x]=1LL*h[x^(1<<lb[x])]*(1<<num[B[lb[x]+1]&i])%mod; if(g[x]) ins((1<<n)-1-i-x,(1<<n)-1-x,1LL*g[x]*h[x]%mod); } } for(int i=0;i<1<<n;++i) { for(int j=head[i];j;j=e[j].next) f[e[j].to]=(f[e[j].to]+1LL*f[i]*e[j].w)%mod; } printf("%d\n",f[(1<<n)-1]); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Games on DAG |
User | FallDream |
Language | C++14 (GCC 5.4.1) |
Score | 1600 |
Code Size | 1292 Byte |
Status | AC |
Exec Time | 289 ms |
Memory | 76800 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1600 / 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 | 137 ms | 1408 KB |
1_02.txt | AC | 137 ms | 1280 KB |
1_03.txt | AC | 289 ms | 76800 KB |
1_04.txt | AC | 279 ms | 74752 KB |
1_05.txt | AC | 285 ms | 76800 KB |
1_06.txt | AC | 238 ms | 60416 KB |
1_07.txt | AC | 271 ms | 70656 KB |
1_08.txt | AC | 284 ms | 76800 KB |
1_09.txt | AC | 276 ms | 74752 KB |
1_10.txt | AC | 281 ms | 74752 KB |
1_11.txt | AC | 264 ms | 68608 KB |
1_12.txt | AC | 281 ms | 76800 KB |
1_13.txt | AC | 281 ms | 76800 KB |
1_14.txt | AC | 284 ms | 76800 KB |
1_15.txt | AC | 267 ms | 70656 KB |
1_16.txt | AC | 265 ms | 68608 KB |
1_17.txt | AC | 283 ms | 76800 KB |
1_18.txt | AC | 230 ms | 56320 KB |
1_19.txt | AC | 283 ms | 76800 KB |
1_20.txt | AC | 148 ms | 11264 KB |
1_21.txt | AC | 2 ms | 640 KB |
1_22.txt | AC | 202 ms | 39936 KB |
1_23.txt | AC | 216 ms | 50176 KB |
1_24.txt | AC | 54 ms | 8832 KB |
1_25.txt | AC | 1 ms | 384 KB |
1_26.txt | AC | 257 ms | 62464 KB |
1_27.txt | AC | 9 ms | 2048 KB |
1_28.txt | AC | 139 ms | 2688 KB |
1_29.txt | AC | 27 ms | 10752 KB |
1_30.txt | AC | 7 ms | 384 KB |
1_31.txt | AC | 273 ms | 72704 KB |
1_32.txt | AC | 26 ms | 8704 KB |
1_33.txt | AC | 8 ms | 1792 KB |
1_34.txt | AC | 63 ms | 14976 KB |
1_35.txt | AC | 26 ms | 8704 KB |