Submission #1829426
Source Code Expand
#include <iostream> #include <cstdio> #include <cstring> #define NDEBUG #include <cassert> #include <cctype> using namespace std; typedef long long lint; #define cout cerr #define ni (next_num<int>()) template<class T>inline T next_num(){ T i=0;char c; while(!isdigit(c=getchar())&&c!='-'); bool flag=c=='-'; flag?c=getchar():0; while(i=i*10-'0'+c,isdigit(c=getchar())); return flag?-i:i; } template<class T1,class T2>inline void apmax(T1 &a,const T2 &b){if(a<b)a=b;} template<class T1,class T2>inline void apmin(T1 &a,const T2 &b){if(b<a)a=b;} const int O=1000000007; int gcd(int a,int b){ return b?gcd(b,a%b):a; } inline int fpow(int x,int n){ int a=1; for(;n;n>>=1,x=(lint)x*x%O){ if(n&1){ a=(lint)a*x%O; } } return a; } inline int inv(int x){ return fpow(x,O-2); } const int N=210; int c[N][N]; int k,f[N],g[N],pw[N],ans=1; namespace G{ const int N=55,E=110*2; int to[E],bro[E],head[N],e=0; int dfn[N],tim=0; int esize[E],estat[E]; int estk[N],ss=0; inline void init(){ memset(head,-1,sizeof(head)); memset(dfn,0,sizeof(dfn)); memset(estat,0,sizeof(estat)); } inline void ae(int u,int v){ to[e]=v,bro[e]=head[u],esize[e]=1,head[u]=e++; } inline void add(int u,int v){ ae(u,v),ae(v,u); } void dfs(int x,int fa){ dfn[x]=++tim; for(int i=head[x],v;~i;i=bro[i]){ if((v=to[i])!=fa){ if(dfn[v]==0){ estk[ss++]=i; ans=(lint)ans*k%O; dfs(v,x); if(estk[ss-1]==i){ ss--; } }else if(dfn[v]<dfn[x]){ int last=i,e,stat=1; do{ e=estk[--ss]; if(estat[e]){ stat=2; ans=(lint)ans*inv((estat[e]==1?f:g)[esize[e]])%O; }else{ ans=(lint)ans*inv(k)%O; } esize[e]+=esize[last],last=e; }while(dfn[v]<dfn[to[e^1]]); estat[e]=stat; estk[ss++]=e; ans=(lint)ans*(stat==1?f:g)[esize[e]]%O; } } } } } inline void gmath(int n,int k){ pw[0]=1; for(int i=1;i<=n;i++){ pw[i]=(lint)pw[i-1]*k%O; } for(int i=1;i<=n;i++){ lint tmp=0; for(int j=0;j<i;j++){ tmp+=pw[gcd(i,j)]; } f[i]=tmp%O*inv(i)%O; } memset(c,0,sizeof(c)); for(int i=0,ti=n+k;i<=ti;i++){ c[i][0]=1; for(int j=1;j<=i;j++){ c[i][j]=(c[i-1][j-1]+c[i-1][j])%O; } } for(int i=1;i<=n;i++){ g[i]=c[i+k-1][k-1]; } } int main(){ int n=ni,m=ni; G::init(); gmath(m,k=ni); for(int i=1;i<=m;G::add(ni,ni),i++); for(int i=1;i<=n;i++){ if(G::dfn[i]==0){ G::dfs(i,0); } } printf("%d\n",ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Painting Graphs with AtCoDeer |
User | sshockwave |
Language | C++14 (GCC 5.4.1) |
Score | 1300 |
Code Size | 2569 Byte |
Status | AC |
Exec Time | 1 ms |
Memory | 384 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1300 / 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 | 384 KB |
0_001.txt | AC | 1 ms | 384 KB |
0_002.txt | AC | 1 ms | 384 KB |
1_003.txt | AC | 1 ms | 384 KB |
1_004.txt | AC | 1 ms | 384 KB |
1_005.txt | AC | 1 ms | 384 KB |
1_006.txt | AC | 1 ms | 384 KB |
1_007.txt | AC | 1 ms | 384 KB |
1_008.txt | AC | 1 ms | 384 KB |
1_009.txt | AC | 1 ms | 384 KB |
1_010.txt | AC | 1 ms | 384 KB |
1_011.txt | AC | 1 ms | 384 KB |
1_012.txt | AC | 1 ms | 384 KB |
1_013.txt | AC | 1 ms | 384 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 | 1 ms | 384 KB |
1_019.txt | AC | 1 ms | 384 KB |
1_020.txt | AC | 1 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 | AC | 1 ms | 384 KB |
1_027.txt | AC | 1 ms | 384 KB |
1_028.txt | AC | 1 ms | 384 KB |
1_029.txt | AC | 1 ms | 384 KB |
1_030.txt | AC | 1 ms | 384 KB |
1_031.txt | AC | 1 ms | 384 KB |
1_032.txt | AC | 1 ms | 384 KB |
1_033.txt | AC | 1 ms | 384 KB |
1_034.txt | AC | 1 ms | 384 KB |
1_035.txt | AC | 1 ms | 384 KB |
1_036.txt | AC | 1 ms | 384 KB |
1_037.txt | AC | 1 ms | 384 KB |
1_038.txt | AC | 1 ms | 384 KB |
1_039.txt | AC | 1 ms | 384 KB |
1_040.txt | AC | 1 ms | 384 KB |
1_041.txt | AC | 1 ms | 384 KB |
1_042.txt | AC | 1 ms | 384 KB |
1_043.txt | AC | 1 ms | 384 KB |
1_044.txt | AC | 1 ms | 384 KB |
1_045.txt | AC | 1 ms | 384 KB |
1_046.txt | AC | 1 ms | 384 KB |
1_047.txt | AC | 1 ms | 384 KB |
1_048.txt | AC | 1 ms | 384 KB |
1_049.txt | AC | 1 ms | 384 KB |
1_050.txt | AC | 1 ms | 384 KB |
1_051.txt | AC | 1 ms | 384 KB |
1_052.txt | AC | 1 ms | 384 KB |
1_053.txt | AC | 1 ms | 384 KB |
1_054.txt | AC | 1 ms | 384 KB |
1_055.txt | AC | 1 ms | 384 KB |
1_056.txt | AC | 1 ms | 384 KB |
1_057.txt | AC | 1 ms | 384 KB |
1_058.txt | AC | 1 ms | 384 KB |
1_059.txt | AC | 1 ms | 384 KB |
1_060.txt | AC | 1 ms | 384 KB |
1_061.txt | AC | 1 ms | 384 KB |
1_062.txt | AC | 1 ms | 384 KB |
1_063.txt | AC | 1 ms | 384 KB |