Submission #3231313

---

Source Code Expand

#include<bits/stdc++.h>
#define mod 1000000007
#define N 1005
#define M 10005
#define ll long long
using namespace std;
inline int read(){
	int ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
struct edge{int v,next;}e[M<<1];
ll ifac[M],fac[M],dfn[N],low[N],tot=0,ans=1;
int n,m,k,top=0,first[N],cnt=0,stk[N],siz,rec,pot,edg;
set<int>tmp;
inline void add(int u,int v){e[++cnt].v=v,e[cnt].next=first[u],first[u]=cnt;}
inline ll ksm(ll x,int p){
	ll ret=1;
	while(p){
		if(p&1)ret=ret*x%mod;
		x=x*x%mod,p>>=1;
	}
	return ret;
}
inline ll gcd(ll a,ll b){while(b){ll t=a;a=b,b=t%a;};return a;}
inline ll polya(int x){
	ll ret=0;
	for(int i=1;i<=x;++i)(ret+=ksm(k,gcd(x,i)))%=mod;
	return ret*ksm(x,mod-2)%mod;
}
inline ll C(int n,int m){return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
inline void dfs(int p,int fa){
	dfn[p]=low[p]=++tot,stk[++top]=p;
	for(int i=first[p];i;i=e[i].next){
		int v=e[i].v;
		if(v==fa)continue;
		if(dfn[v]){low[p]=min(low[p],dfn[v]);continue;}
		dfs(v,p),low[p]=min(low[p],low[v]);
		if(low[v]>=dfn[p]){
			tmp.clear(),pot=edg=0;
			do tmp.insert((rec=stk[top--])),++pot; while(rec!=v);
			tmp.insert(p),++pot;
			for(set<int>:: iterator it=tmp.begin();it!=tmp.end();++it)for(int k=first[*it];k;k=e[k].next)if(tmp.count(e[k].v))++edg;
			edg>>=1;
			ll ttmp;
			if(edg<pot)(ans*=k)%=mod;
			if(edg==pot)(ans*=polya(edg))%=mod;
			if(edg>pot)(ans*=C(edg+k-1,k-1))%=mod;
		}
	}
	if(!fa)--top;
}
int main(){
	n=read(),m=read(),k=read(),ifac[0]=fac[0]=ifac[1]=1;
	for(int i=2;i<M;++i)ifac[i]=(mod-mod/i)*ifac[mod%i]%mod;
	for(int i=1;i<M;++i)fac[i]=fac[i-1]*i%mod,(ifac[i]*=ifac[i-1])%=mod;
	for(int i=1;i<=m;++i){
		int a=read(),b=read();
		add(a,b),add(b,a);
	}
	for(int i=1;i<=n;++i)if(!dfn[i])dfs(i,0);
	cout<<ans;
	return 0;
}

Submission Info

Judge Result