Submission #1193136


Source Code Expand

#include <cstdio>
#include <algorithm>
#define N 53
#define M 207
#define IL inline
#define REP(a,b,c) for(a=b;a<=c;a++)
#define PER(a,b,c) for(a=b;a>=c;a--)
using namespace std;
typedef long long lol;
const int mod=1e9+7;
int n,m,k,dfn[N],low[N],tk,S[M],top;
int head[N],lt[M],nt[M],ap=1,pw[N],vis[N],col;
lol fac[M],inv[M],ans=1;
IL int gcd(int a,int b){int t;while(b)t=a%b,a=b,b=t;return a;}
IL lol qpow(lol a,int b){lol res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod,b>>=1;}return res;}
IL void link(int a,int b){
	lt[++ap]=b,nt[ap]=head[a],head[a]=ap;
	lt[++ap]=a,nt[ap]=head[b],head[b]=ap;
}
IL int rd(){
	int res=0;char c;while((c=getchar())<'0'||c>'9');
	while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();return res;
}
IL lol polya(int n){
	int i,res=0;
	REP(i,1,n)res=(res+pw[gcd(i,n)])%mod;
	return res*qpow(n,mod-2)%mod;
}
IL lol C(int n,int m){return fac[n]*inv[m]%mod*inv[n-m]%mod;}
IL void solve(int x){
	if(top==1)ans=ans*k%mod,top=0;
	else{
		int u,v,etot=0,vtot=0;++col;
		do{
			etot++;
			u=lt[S[top]],v=lt[S[top]^1];
			if(vis[u]!=col)vtot++,vis[u]=col;
			if(vis[v]!=col)vtot++,vis[v]=col;
		}while(S[top--]!=x);
		if(etot==vtot)ans=(ans*polya(etot))%mod;
		else ans=ans*C(etot+k-1,k-1)%mod;
	}
}
IL void tarjan(int u,int f){
	dfn[u]=low[u]=++tk;int x,v;
	for(x=head[u];x;x=nt[x])if((v=lt[x])!=f){
			if(!dfn[v]){
				S[++top]=x;tarjan(v,u),low[u]=min(low[u],low[v]);
				if(low[v]>=dfn[u])solve(x);
			}
			else{
				low[u]=min(low[u],dfn[v]);
				if(dfn[v]<dfn[u])S[++top]=x;
			}
		}
}
int main(){
  n=rd(),m=rd(),k=rd();int i,j=m+k;fac[0]=pw[0]=1;
  REP(i,1,j)fac[i]=fac[i-1]*i%mod;inv[j]=qpow(fac[j],mod-2);
	PER(i,j,1)inv[i-1]=inv[i]*i%mod;REP(i,1,n)pw[i]=(1LL*pw[i-1]*k)%mod;
	REP(i,1,m)link(rd(),rd());
	REP(i,1,n)if(!dfn[i])
		tarjan(i,0);
	printf("%lld",ans);
  return 0;
}

Submission Info

Submission Time
Task F - Painting Graphs with AtCoDeer
User mytryer
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 1868 Byte
Status AC
Exec Time 1 ms
Memory 128 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1300 / 1300
Status
AC × 3
AC × 64
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 128 KB
0_001.txt AC 1 ms 128 KB
0_002.txt AC 1 ms 128 KB
1_003.txt AC 1 ms 128 KB
1_004.txt AC 1 ms 128 KB
1_005.txt AC 1 ms 128 KB
1_006.txt AC 1 ms 128 KB
1_007.txt AC 1 ms 128 KB
1_008.txt AC 0 ms 128 KB
1_009.txt AC 1 ms 128 KB
1_010.txt AC 1 ms 128 KB
1_011.txt AC 1 ms 128 KB
1_012.txt AC 1 ms 128 KB
1_013.txt AC 1 ms 128 KB
1_014.txt AC 1 ms 128 KB
1_015.txt AC 1 ms 128 KB
1_016.txt AC 1 ms 128 KB
1_017.txt AC 1 ms 128 KB
1_018.txt AC 1 ms 128 KB
1_019.txt AC 1 ms 128 KB
1_020.txt AC 1 ms 128 KB
1_021.txt AC 1 ms 128 KB
1_022.txt AC 1 ms 128 KB
1_023.txt AC 1 ms 128 KB
1_024.txt AC 1 ms 128 KB
1_025.txt AC 1 ms 128 KB
1_026.txt AC 0 ms 128 KB
1_027.txt AC 1 ms 128 KB
1_028.txt AC 0 ms 128 KB
1_029.txt AC 1 ms 128 KB
1_030.txt AC 1 ms 128 KB
1_031.txt AC 1 ms 128 KB
1_032.txt AC 1 ms 128 KB
1_033.txt AC 1 ms 128 KB
1_034.txt AC 1 ms 128 KB
1_035.txt AC 1 ms 128 KB
1_036.txt AC 1 ms 128 KB
1_037.txt AC 1 ms 128 KB
1_038.txt AC 1 ms 128 KB
1_039.txt AC 1 ms 128 KB
1_040.txt AC 0 ms 128 KB
1_041.txt AC 1 ms 128 KB
1_042.txt AC 1 ms 128 KB
1_043.txt AC 1 ms 128 KB
1_044.txt AC 1 ms 128 KB
1_045.txt AC 1 ms 128 KB
1_046.txt AC 1 ms 128 KB
1_047.txt AC 1 ms 128 KB
1_048.txt AC 1 ms 128 KB
1_049.txt AC 1 ms 128 KB
1_050.txt AC 1 ms 128 KB
1_051.txt AC 1 ms 128 KB
1_052.txt AC 1 ms 128 KB
1_053.txt AC 1 ms 128 KB
1_054.txt AC 1 ms 128 KB
1_055.txt AC 1 ms 128 KB
1_056.txt AC 1 ms 128 KB
1_057.txt AC 1 ms 128 KB
1_058.txt AC 1 ms 128 KB
1_059.txt AC 1 ms 128 KB
1_060.txt AC 1 ms 128 KB
1_061.txt AC 1 ms 128 KB
1_062.txt AC 1 ms 128 KB
1_063.txt AC 1 ms 128 KB