Submission #932188

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;
const ll MOD = 1e9 + 7;
int n, m, k;
vector<int> eds[100];
int h[100];
int was[100];
int was1[100];
int cl[100];
vector<pair<int, int> > ed2;
ll dp1[120];
ll cnk[220][220];

ll pw(ll a, ll b) {
	ll ans = 1;
	while (b) {
		while (!(b & 1))
			b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD;
		--b;
	}
	return ans;
}

void dfs1(int v, int hh = 0) {
	h[v] = hh;
	was1[v] = 1;
	for (int u: eds[v])
		if (!was1[u])
			dfs1(u, hh + 1);
}
ll gans = 1;


void upd(vector<int> vv) {
	int cnt = 0;
	memset(cl, 0, sizeof(cl));
	for (int i: vv)
		cl[i] = 1;
	for (pair<int, int> i: ed2) {
		if (cl[i.first] && cl[i.second])
			++cnt;
	}
	ll ans = 0;
	if (cnt == (int)vv.size()) {
		for (int j = 1; j <= cnt; ++j)
			if (cnt % j == 0)
				ans = (ans + dp1[j]) % MOD;
	}
	else {
		ans = cnk[cnt + k - 1][k - 1];
	}
	gans = (gans * ans) % MOD;
}

pair<int, vector<int> > dfs2(int v) {
	was[v] = 1;
	vector<int> ans;
	ans.push_back(v);
	int mx = h[v];
	for (int u: eds[v]) {
		if (!was[u]) {
			pair<int, vector<int> > tmp = dfs2(u);
			if (tmp.first < h[v]) {
				mx = min(mx, tmp.first);
				for (int x: tmp.second)
					ans.push_back(x);
			}
			else if (tmp.first == h[v]) {
				tmp.second.push_back(v);
				upd(tmp.second);
			}
			else {
				gans = (gans * k) % MOD;
			}
		}
		else {
			mx = min(mx, h[u]);
		}
	}
	return make_pair(mx, ans);
}

int main() {
	cin >> n >> m >> k;
	dp1[0] = 0;
	for (int i = 1; i <= n; ++i) {
		dp1[i] = 1;
		for (int j = 0; j < i; ++j)
			dp1[i] = (dp1[i] * k) % MOD;
		for (int j = 1; j < i; ++j)
			if (i % j == 0)
				dp1[i] = (dp1[i] - dp1[j] + MOD) % MOD;
	}
	for (int i = 1; i <= n; ++i) {
		dp1[i] = (dp1[i] * pw(i, MOD - 2)) % MOD;
	}
	for (int i = 0; i < 220; ++i)
		for (int j = 0; j < 220; ++j) {
			if (i == j || j == 0)
				cnk[i][j] = 1;
			else if (j > i)
				cnk[i][j] = 0;
			else
				cnk[i][j] = (cnk[i - 1][j] + cnk[i - 1][j - 1]) % MOD;
		}
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		--a, --b;
		eds[a].push_back(b);
		eds[b].push_back(a);
		ed2.push_back(make_pair(a, b));
	}
	for (int i = 0; i < n; ++i) {
		if (was1[i])
			continue;
		dfs1(i);
		auto x = dfs2(i);
		if ((int)x.second.size() != 1) {
			upd(x.second);
		}
	}
	cout << gans << "\n";
	return 0;
}

Submission Info

Judge Result