Submission #1015868

---

Source Code Expand

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

const int mod = 1000000007;

long long modpow(long long x, int y) {
	if (y == 0) return 1;
	if (y == 1) return x;
	long long z = modpow(x, y/2);
	z = z*z % mod;
	if (y % 2) z = z*x % mod;
	return z;
}

long long modinv(long long x) {
	return modpow(x, mod-2);
}

long long modfact(int n) {
	long long r = 1;
	for (int i = 1; i <= n; ++ i) r = r*i % mod;
	return r;
}

long long modcomb(int n, int k) {
	return modfact(n) * modinv(modfact(k)) % mod * modinv(modfact(n-k)) % mod;
}

struct BComp {
	const vector<vector<int>>& G;
	vector<int> ord;
	vector<int> low;
	vector<pair<int,int>> S;
	vector<vector<pair<int,int>>> bcomp;

	BComp(const vector<vector<int>>& G) : G(G), ord(G.size(),-1), low(G.size()) {
		for (int u = 0; u < (int)G.size(); ++ u) if (ord[u] == -1) {
			ord[u] = low[u] = 0;
			dfs(u, -1);
		}
	}

	int dfs(int u, int p) {
		int cnt=1;
		for (int v : G[u]) if(v != p) {
			if (ord[v] < ord[u])
				S.emplace_back(u,v);
			if (ord[v] == -1) {
				ord[v] = low[v] = ord[u]+cnt;
				cnt += dfs(v, u);
				low[u] = min(low[u],low[v]);
				if (ord[u] <= low[v]) {
					bcomp.emplace_back();
					for (;;) {
						auto e = S.back(); S.pop_back();
						bcomp.back().push_back(e);
						if(e == make_pair(u,v)) break;
					}
				}
			} else {
				low[u] = min(low[u],ord[v]);
			}
		}
	}
};

bool iscycle(const vector<pair<int,int>>& x) {
	set<int> s;
	for (auto p : x) {
		s.insert(p.first);
		s.insert(p.second);
	}
	return s.size() == x.size();
}

int main() {
	int N, M, K;
	vector<vector<int>> G;
	cin >> N >> M >> K;
	G.resize(N);
	for (int i = 0; i < M; ++ i) {
		int x, y;
		cin >> x >> y;
		-- x; -- y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	BComp a(G);
	long long r = 1;
	for (const auto& x : a.bcomp) {
		if (x.size() == 1) {
			r = (r * K) % mod;
		} else if (iscycle(x)) {
			int n = x.size();
			long long rr = 0;
			for (int i = 0; i < n; ++ i) {
				rr = (rr + modpow(K, __gcd(n, i))) % mod;
			}
			rr = rr * modinv(n) % mod;
			r = (r * rr) % mod;
		} else {
			int m = x.size();
			r = (r * modcomb(m+K-1, K-1)) % mod;
		}
	}
	cout << r << endl;
}

Submission Info

Judge Result