Submission #932522

---

Source Code Expand

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

const int mod = 1e9 + 7;
const int N = 50;

int n, m, K;
vector<int> g[N];

int low[N], ord[N];
stack<pair<int, int>> stk;
vector<vector<pair<int, int>>> cc;

int gcd(int x, int y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}

int add(int x, int y) {
	x += y;
	return x >= mod ? x - mod : x;
}

int mul(int x, int y) {
	return int64_t(x) * y % mod;
}

int modpow(int a, long long b) {
	if (b == 0) return 1;
	return mul(modpow(mul(a, a), b / 2), b & 1 ? a : 1);
}

int modinv(int a) {
	return modpow(a, mod - 2);
}

void dfs(int u, int p, int &k) {
	low[u] = ord[u] = k++;

	for (int v : g[u]) {
		if (ord[v] == -1) {
			stk.emplace(u, v);
			dfs(v, u, k);
			low[u] = min(low[u], low[v]);
			if (p == -1 || ord[u] <= low[v]) {
				cc.push_back(vector<pair<int, int>>());
				while (!stk.empty()) {
					auto e = stk.top();
					stk.pop();
					cc.back().emplace_back(e);
					if (e.first == u) break;
				}
			}
		} else if (v != p && ord[v] < ord[u]) {
			stk.emplace(u, v);
			low[u] = min(low[u], ord[v]);
		}
	}
}

int main() {
	cin >> n >> m >> K;

	for (int i = 0; i < m; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		u--; v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	memset(ord, -1, sizeof(ord));
	int k = 0;

	for (int i = 0; i < n; i++) {
		if (ord[i] == -1) dfs(i, -1, k);
	}

	static int C[500][500];
	for (int i = 0; i < 500; i++) {
		for (int j = 0; j <= i; j++) {
			if (i == 0 || j == 0) C[i][j] = 1;
			else C[i][j] = add(C[i - 1][j - 1], C[i - 1][j]);
		}
	}

	int ans = 1;
	for (auto c : cc) {
		int m = c.size();

		if (m == 1) {
			ans = mul(ans, K);
			continue;
		}
		
		set<int> vs;
		for (auto e : c) {
			vs.insert(e.first);
			vs.insert(e.second);
		}
		
		if (m == vs.size()) {
			int sum = 0;
			for (int i = 0; i < m; i++) {
				sum = add(sum, modpow(K, gcd(m, i)));
			}
			sum = mul(sum, modinv(m));
			ans = mul(ans, sum);
		} else {
			// H(k,m)=C(k+m-1,m)
			ans = mul(ans, C[K + m - 1][m]);
		}
	}

	cout << ans << endl;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:66:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
                         ^

Judge Result