Submission #1651283
Source Code Expand
#include<bits/stdc++.h> #define ll long long #define mod 1000000007 #define N 109 using namespace std; int n,m,K,tot=1,fst[N],pnt[N<<1],nxt[N<<1],dad[N],d[N],eg[N]; int cbn[N<<1][N<<1],fa[N],sum[N],sz[N]; bool vis[N],bo[N]; int gcd(int x,int y){ return y?gcd(y,x%y):x; } int ksm(int x,int y){ int z=1; for (; y; y>>=1,x=(ll)x*x%mod) if (y&1) z=(ll)z*x%mod; return z; } void add(int x,int y){ pnt[++tot]=y; nxt[tot]=fst[x]; fst[x]=tot; } int getfa(int x){ return x==fa[x]?x:fa[x]=getfa(fa[x]); } void mrg(int x,int y){ x=getfa(x); y=getfa(y); sz[y]+=sz[x]; sum[y]+=sum[x]; fa[x]=y; } void dfs(int x,int p){ int i,y; vis[x]=1; for (i=fst[x]; i; i=nxt[i]) if (i^p^1){ y=pnt[i]; if (!vis[y]){ dad[y]=x; d[y]=d[x]+1; eg[y]=i>>1; bo[i>>1]=1; sz[i>>1]=0; dfs(y,i); } } } int main(){ scanf("%d%d%d",&n,&m,&K); int i,j,x,y; for (i=0; i<=n+K; i++) for (j=cbn[i][0]=1; j<=i; j++) cbn[i][j]=(cbn[i-1][j]+cbn[i-1][j-1])%mod; for (i=1; i<=m; i++){ scanf("%d%d",&x,&y); add(x,y); add(y,x); } for (i=1; i<=m; i++){ fa[i]=i; sz[i]=sum[i]=1; } for (i=1; i<=n; i++) if (!vis[i]) dfs(i,0); for (i=1; i<=m; i++) if (!bo[i]){ x=pnt[i<<1]; y=pnt[i<<1|1]; if (d[x]<d[y]) swap(x,y); for (; x!=y; x=dad[x]) mrg(eg[x],i); } int ans=1; for (i=1; i<=m; i++) if (getfa(i)==i){ if (sz[i]>1) ans=(ll)ans*cbn[sum[i]+K-1][K-1]%mod; else{ for (j=1,x=0; j<=sum[i]; j++) x=(x+ksm(K,gcd(j,sum[i])))%mod; ans=(ll)ans*x%mod*ksm(sum[i],mod-2)%mod; } } printf("%d\n",ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Painting Graphs with AtCoDeer |
User | lych_cys |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1582 Byte |
Status | RE |
Exec Time | 109 ms |
Memory | 384 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:34:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d%d",&n,&m,&K); ^ ./Main.cpp:40:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d",&x,&y); ^
Judge Result
Set Name | Sample | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 1300 | ||||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 0_000.txt, 0_001.txt, 0_002.txt |
All | 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt, 1_042.txt, 1_043.txt, 1_044.txt, 1_045.txt, 1_046.txt, 1_047.txt, 1_048.txt, 1_049.txt, 1_050.txt, 1_051.txt, 1_052.txt, 1_053.txt, 1_054.txt, 1_055.txt, 1_056.txt, 1_057.txt, 1_058.txt, 1_059.txt, 1_060.txt, 1_061.txt, 1_062.txt, 1_063.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_000.txt | AC | 1 ms | 256 KB |
0_001.txt | AC | 1 ms | 256 KB |
0_002.txt | AC | 1 ms | 256 KB |
1_003.txt | AC | 1 ms | 256 KB |
1_004.txt | AC | 2 ms | 384 KB |
1_005.txt | AC | 2 ms | 384 KB |
1_006.txt | RE | 102 ms | 384 KB |
1_007.txt | AC | 1 ms | 256 KB |
1_008.txt | AC | 1 ms | 256 KB |
1_009.txt | AC | 1 ms | 256 KB |
1_010.txt | AC | 1 ms | 256 KB |
1_011.txt | AC | 1 ms | 256 KB |
1_012.txt | RE | 108 ms | 256 KB |
1_013.txt | RE | 109 ms | 256 KB |
1_014.txt | AC | 1 ms | 384 KB |
1_015.txt | AC | 1 ms | 384 KB |
1_016.txt | AC | 1 ms | 384 KB |
1_017.txt | AC | 1 ms | 384 KB |
1_018.txt | AC | 2 ms | 384 KB |
1_019.txt | RE | 109 ms | 384 KB |
1_020.txt | RE | 102 ms | 384 KB |
1_021.txt | AC | 1 ms | 384 KB |
1_022.txt | AC | 1 ms | 384 KB |
1_023.txt | AC | 1 ms | 384 KB |
1_024.txt | AC | 1 ms | 384 KB |
1_025.txt | AC | 1 ms | 384 KB |
1_026.txt | RE | 101 ms | 384 KB |
1_027.txt | RE | 103 ms | 384 KB |
1_028.txt | AC | 1 ms | 256 KB |
1_029.txt | RE | 102 ms | 256 KB |
1_030.txt | RE | 101 ms | 256 KB |
1_031.txt | RE | 102 ms | 256 KB |
1_032.txt | AC | 1 ms | 256 KB |
1_033.txt | RE | 102 ms | 256 KB |
1_034.txt | RE | 102 ms | 256 KB |
1_035.txt | RE | 103 ms | 256 KB |
1_036.txt | AC | 1 ms | 384 KB |
1_037.txt | WA | 1 ms | 384 KB |
1_038.txt | WA | 1 ms | 384 KB |
1_039.txt | WA | 1 ms | 384 KB |
1_040.txt | AC | 1 ms | 256 KB |
1_041.txt | RE | 101 ms | 256 KB |
1_042.txt | RE | 104 ms | 256 KB |
1_043.txt | RE | 102 ms | 256 KB |
1_044.txt | AC | 1 ms | 256 KB |
1_045.txt | RE | 104 ms | 256 KB |
1_046.txt | RE | 103 ms | 256 KB |
1_047.txt | RE | 103 ms | 256 KB |
1_048.txt | AC | 1 ms | 384 KB |
1_049.txt | RE | 104 ms | 384 KB |
1_050.txt | RE | 106 ms | 384 KB |
1_051.txt | RE | 103 ms | 384 KB |
1_052.txt | AC | 1 ms | 256 KB |
1_053.txt | RE | 102 ms | 256 KB |
1_054.txt | WA | 1 ms | 256 KB |
1_055.txt | WA | 1 ms | 256 KB |
1_056.txt | AC | 1 ms | 256 KB |
1_057.txt | RE | 106 ms | 256 KB |
1_058.txt | RE | 102 ms | 256 KB |
1_059.txt | RE | 106 ms | 256 KB |
1_060.txt | AC | 2 ms | 384 KB |
1_061.txt | RE | 101 ms | 384 KB |
1_062.txt | RE | 102 ms | 384 KB |
1_063.txt | RE | 102 ms | 384 KB |