Submission #1865435

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define forE(i,x) for(int i=head[x];i!=-1;i=ne[i])
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned u32;
typedef pair<int,int> pin;
#define mk(a,b) make_pair(a,b)
#define lowbit(x) ((x)&(-(x)))
#define sqr(a) ((a)*(a))
#define clr(a) (memset((a),0,sizeof(a)))
#define ls ((x)<<1)
#define rs (((x)<<1)|1)
#define mid (((l)+(r))>>1)
#define pb push_back
#define w1 first
#define w2 second
inline void read(int &x){
	x=0;int 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();}
	x*=f;
}
inline void judge(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
}
/*******************************head*******************************/
const int maxn=205;
int head[maxn],t[maxn<<1],ne[maxn<<1],num,C[maxn][maxn],dfn[maxn],low[maxn],S[maxn];
bool vis[maxn],ins[maxn];
const int mod=1e9+7;
inline int powmod(int a,int b){
	int res=1;for(;b;b>>=1){
		if(b&1)res=1ll*res*a%mod;
		a=1ll*a*a%mod;
	}return res;
}

inline void addedge(int x,int y){
	ne[++num]=head[x];head[x]=num;t[num]=y;
	ne[++num]=head[y];head[y]=num;t[num]=x;
}
bool flag[maxn];
int ans,n,m,k,clk,top;
inline void calc(int x,int y){
	int cntv=0,cnte=0;
	memset(flag,0,sizeof(flag));cntv=flag[y]=1;
    for(;S[top+1]!=x;flag[S[top--]]=1,++cntv);
    rep(w,1,n)if(flag[w])forE(i,w)cnte+=flag[t[i]];cnte/=2;
	if(cnte<cntv){
		ans=1ll*ans*k%mod;
		return;
	}
	if(cnte>cntv){
		ans=1ll*ans*C[cnte+k-1][k-1]%mod;
		return;
	}
	int res=0;
	rep(i,1,cntv){
		res=(res+powmod(k,__gcd(i,cntv)))%mod;
	}
	ans=1ll*res*ans%mod*powmod(cntv,mod-2)%mod;
}
inline void dfs(int x){
    S[++top]=x;dfn[x]=low[x]=++clk;
    forE(i,x)
        if (dfn[t[i]])
            low[x]=min(low[x],dfn[t[i]]);
        else{
            dfs(t[i]),low[x]=min(low[x],low[t[i]]);
            if (low[t[i]]>=dfn[x])
                calc(t[i],x);
		}
}
inline void prprpr(){
	rep(i,0,200){
		C[i][0]=1;
		rep(j,1,i)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	}
}
int main(){
	read(n);read(m);read(k);
	rep(i,1,n)head[i]=-1;
	rep(i,1,m){
		int x,y;read(x);read(y);
		addedge(x,y);
	}prprpr();ans=1;
	rep(i,1,n)if(!dfn[i])dfs(i);
	printf("%d\n",ans);
	return 0;
}

Submission Info

Judge Result