Submission #950547

---

Source Code Expand

#include <iostream>
#include <vector>
#include <set>
#include <stack>
#include <functional>

using namespace std;

const int MOD = 1000000007;

struct Edge {
	Edge(int src, int dst) : src(src), dst(dst) {}
	int src, dst;
	int getMin() const { return min(src, dst); }
	int getMax() const { return max(src, dst); }
	bool operator < (const Edge& e) const {
		if(getMin() == e.getMin()){
			return getMax() < e.getMax();
		}
		return getMin() < e.getMin();
	}
};

int gcd(int a, int b){ return a%b ? gcd(b, a%b) : b; }

vector< set<Edge> > findArt(const vector< vector<int> >& g){
	const int n = g.size();
	vector<int> order(n, -1), low(n, -1);
	vector< set<Edge> > comp;
	stack<Edge> edges;
	int time = 0;

	function<void(int)> f = [&](int v){
		order[v] = low[v] = time;
		++time;
		for(int i=0;i<g[v].size();i++){
			const int dst = g[v][i];
			if(order[dst] < order[v]) edges.push(Edge(v, dst));
			if(order[dst] == -1){
				f(dst);
				low[v] = min(low[v], low[dst]);
				if(order[v] <= low[dst]){
					comp.push_back(set<Edge>());
					while(true){
						Edge e = edges.top(); edges.pop();
						comp.back().insert(e);
						if(e.src == v && e.dst == dst) break;
					}
				}
			} else {
				low[v] = min(low[v], order[dst]);
			}
		}
	};

	for(int i=0;i<n;i++){
		if(order[i] != -1) continue;
		time = 0;
		f(i);
	}

	return comp;
}

long long modPow(long long a, long long p){
	if(p == 0) return 1;
	long long r = modPow(a, p/2);
	r = r*r%MOD;
	if(p%2 == 1) r = r*a%MOD;
	return r;
}

int main(){
	int N, M, K;
	long long comb[201][202];
	for(int i=1;i<=200;i++){
		comb[i][0] = 1;
		for(int j=1;j<i;j++){
			comb[i][j] = comb[i-1][j-1] + comb[i-1][j];
			comb[i][j] %= MOD;
		}
		comb[i][i] = 1;
	}
	while(cin >> N >> M >> K){
		vector< vector<int> > g(N);
		for(int i=0;i<M;i++){
			int a, b; cin >> a >> b;
			--a; --b;
			g[a].push_back(b);
			g[b].push_back(a);
		}
		vector< set<Edge> > c = findArt(g);
		long long res = 1;
		for(int i=0;i<c.size();i++){
			const set<Edge>& v = c[i];
			if(v.size() == 1){
				res *= K;
				res %= MOD;
				continue;
			}
			set<int> S;
			for(const Edge& e : v){
				S.insert(e.src);
				S.insert(e.dst);
			}
			if(S.size() == v.size()){
				long long add = 0;
				for(int j=1;j<=S.size();j++){
					add += modPow(K, gcd(j, S.size()));
					add %= MOD;
				}
				add *= modPow(S.size(), MOD-2);
				add %= MOD;
				res *= add;
				res %= MOD;
			} else {
				res *= comb[v.size()+K-1][v.size()];
				res %= MOD;
			}
		}
		cout << res << endl;
	}
}

Submission Info

Judge Result