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
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 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