Submission #1692967

---

Source Code Expand

#include <bits/stdc++.h>
#define N 210
#define mod 1000000007
using namespace std;
typedef long long ll;
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;
}
struct edge
{
	int u,v,next;
}vs[N<<1];
int n,m,k,st[N],ee,sta[N],top,las;
int bl[N],dfn[N],low[N],tot,Ans=1,c[N][N];
inline int qpow(int bas,int pw)
{
	int ret=1; for(;pw;pw>>=1,bas=1ll*bas*bas%mod)
		if(pw&1) ret=1ll*bas*ret%mod; return ret;
}
inline void addedge(int u,int v)
{
	vs[++ee].v=v;vs[ee].next=st[u];st[u]=ee;
}
inline int polya(int n)
{
	int ret=0; 
		for(int i=1;i<=n;i++) 
			ret=(ret+qpow(k,__gcd(i,n)))%mod;
	return 1ll*ret*qpow(n,mod-2)%mod;
}
inline void calc(int x,int y)
{
	//cerr << x << " " << y << endl;
	int cnt=1,bcnt=0;
	bl[x]=++tot; while(sta[top]!=y)
		bl[sta[top]]=tot,top--,cnt++;
	top--; bl[y]=tot; cnt++; 
	if(cnt==2) {Ans=1ll*Ans*k%mod; return ;}
	for(int i=1;i<=n;i++) if(bl[i]==tot)
		for(int j=st[i];j;j=vs[j].next)
			if(bl[vs[j].v]==tot) bcnt++;
	bcnt>>=1;
	if(bcnt==cnt) Ans=1ll*Ans*polya(cnt)%mod;
	else Ans=1ll*Ans*c[bcnt+k-1][k-1]%mod;
}
inline void dfs(int rt,int pr)
{
	dfn[rt]=low[rt]=++las; sta[++top]=rt;
	for(int i=st[rt];i;i=vs[i].next)
	{
		if(vs[i].v==pr) continue;
 		if(!dfn[vs[i].v])
		{
			dfs(vs[i].v,rt);low[rt]=min(low[rt],low[vs[i].v]);
			if(low[vs[i].v]>=dfn[rt]) calc(rt,vs[i].v);
		}
		else low[rt]=min(low[rt],dfn[vs[i].v]);
	}
}
int main()
{
	c[0][0]=1; for(int i=1;i<=200;i++)
	{
		c[i][0]=1; for(int j=1;j<=200;j++)
			c[i][j]=(1ll*c[i-1][j]+1ll*c[i-1][j-1])%mod;
	}
	n=read(); m=read(); k=read();
	for(int i=1;i<=m;i++)
	{
		int u=read(), v=read();
		addedge(u,v); addedge(v,u);
	}
	for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i,0);
	cout << Ans << endl;
	return 0 ;
}

Submission Info

Judge Result