Submission #1007360

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define dump(...) cout<<"# "<<#__VA_ARGS__<<'='<<(__VA_ARGS__)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vd=vector<double>;
using vvd=vector<vd>;
using vs=vector<string>;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}

template<typename Tuple>
void print_tuple(ostream&,const Tuple&){}
template<typename Car,typename... Cdr,typename Tuple>
void print_tuple(ostream& os,const Tuple& t){
	print_tuple<Cdr...>(os,t);
	os<<(sizeof...(Cdr)?",":"")<<get<sizeof...(Cdr)>(t);
}
template<typename... Args>
ostream& operator<<(ostream& os,const tuple<Args...>& t){
	print_tuple<Args...>(os<<'(',t);
	return os<<')';
}

template<typename Ch,typename Tr,typename C>
basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){
	os<<'[';
	for(auto i=begin(c);i!=end(c);++i)
		os<<(i==begin(c)?"":" ")<<*i;
	return os<<']';
}

constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;

using Edge=tuple<int,int>;

int dfs(const vvi& g,int p,int u,vi& ord,vi& low,stack<Edge>& s,vector<vector<Edge>>& bc)
{
	int cnt=1;
	low[u]=ord[u];
	for(int v:g[u]) if(v!=p){
		if(ord[v]<ord[u])
			s.emplace(u,v);
		if(ord[v]==-1){
			ord[v]=ord[u]+cnt;
			cnt+=dfs(g,u,v,ord,low,s,bc);
			low[u]=min(low[u],low[v]);
			if(ord[u]<=low[v]){
				bc.emplace_back();
				for(;;){
					Edge e=s.top(); s.pop();
					bc.back().push_back(e);
					if(get<0>(e)==u) break;
				}
			}
		}
		else
			low[u]=min(low[u],ord[v]);
	}
	return cnt;
}

vector<vector<Edge>> decomposition(const vvi& g)
{
	int n=g.size();
	vi ord(n,-1),low(n);
	stack<Edge> s;
	vector<vector<Edge>> bc;
	rep(u,n) if(ord[u]==-1){
		ord[u]=0;
		dfs(g,-1,u,ord,low,s,bc);
	}
	return bc;
}

int ncr(int n,int r)
{
	static int memo[201][101];
	if(memo[n][r]) return memo[n][r];
	if(r==0||r==n) return memo[n][r]=1;
	return memo[n][r]=(ncr(n-1,r-1)+ncr(n-1,r))%MOD;
}

int ModPow(int a,int r,int m)
{
	int x=1;
	for(;r;r>>=1){
		if(r&1) x=(ll)x*a%m;
		a=(ll)a*a%m;
	}
	return x;
}

int ModInverse(int a,int m)
{
	int x=1;
	for(int b=m,u=0;b;){
		ll t=a/b;
		swap(a-=b*t,b);
		swap(x-=u*t,u);
	}
	return (x+m)%m;
}

int ModMul(int a,int b,int m)
{
	return (ll)a*b%m;
}

int ModDiv(int a,int b,int m)
{
	return ModMul(a,ModInverse(b,m),m);
}

int main()
{
	for(int n,m,k;cin>>n>>m>>k&&n|m|k;){
		vvi g(n);
		rep(i,m){
			int u,v; cin>>u>>v; u--,v--;
			g[u].push_back(v);
			g[v].push_back(u);
		}

		ll res=1;
		for(auto es:decomposition(g)){
			if(es.size()==1)
				(res*=k)%=MOD;
			else{
				set<int> vs;
				for(auto e:es){
					vs.insert(get<0>(e));
					vs.insert(get<1>(e));
				}
				if(vs.size()==es.size()){  // cycle
					ll tmp=0;
					rep(i,es.size())
						(tmp+=ModPow(k,__gcd<int>(es.size(),i),MOD))%=MOD;
					(res*=ModDiv(tmp,es.size(),MOD))%=MOD;
				}
				else
					(res*=ncr(k+es.size()-1,es.size()))%=MOD;
			}
		}
		cout<<res<<endl;
	}
}

Submission Info

Judge Result