Submission #1811519

---

Source Code Expand

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

const int N = 55, P = 1e9 + 7, M = 205;

int n, m, k, dfn[N], cn[N], ans = 1, low[N], bl[N], cnt, stu[N], stv[N], top, tot, C[M][M], si[N], Gr[N];

vector<int>V[N];

void Min (int &x, int y) { if (x > y) x = y; }

void Tarjan (int x, int fa) {
	dfn[x] = low[x] = ++cnt;
	for (auto v : V[x]) if (v != fa) {
		if (!dfn[v]) {
			int la = ++top; stu[top] = x; stv[top] = v;
			Tarjan(v, x);
			if (low[v] > dfn[x]) { ans = 1ll * ans * k; top = la - 1; continue ; }
			if (low[v] == dfn[x]) {
				for (++tot; top >= la; --top, ++cn[tot]) {
					if (bl[stu[top]] != tot) {
						bl[stu[top]] = tot;
						++si[tot];
						cn[tot] += Gr[stu[top]];
					}
					if (bl[stv[top]] != tot) {
						bl[stv[top]] = tot;
						++si[tot];
						cn[tot] += Gr[stv[top]];
					}
				}
				cn[tot] -= Gr[x];
			} else Min(low[x], low[v]);
		} else if (dfn[v] <= dfn[x]) Min(low[x], dfn[v]), ++Gr[x];
	}
}

int qp (int a, int b) { int c = 1; for (; b; b >>= 1, a = 1ll * a * a % P) if (b & 1) c = 1ll * c * a % P; return c; }
int gcd (int a, int b) { return b ? gcd(b, a % b) : a; }

int main () {
	scanf("%d%d%d", &n, &m, &k);
	C[0][0] = 1;
	for (int i = 1; i <= m + k; ++i) {
		C[i][0] = 1;
		for (int j = 1; j <= i; ++j) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P;
	}
	for (int i = 0, u, v; i < m; ++i) {
		scanf("%d%d", &u, &v);
		V[u].emplace_back(v);
		V[v].emplace_back(u);
	}
	for (int i = 1; i <= n; ++i) if (!dfn[i]) Tarjan(i, 0);
//	si[2] = 5; cn[2] = 5; ++tot; si[tot] = 4; cn[tot] = 5;
	for (int i = 1; i <= tot; ++i) {
		if (si[i] == 1) continue ;
		if (si[i] != cn[i]) ans = 1ll * ans * C[cn[i] + k - 1][k - 1] % P;
		else {
			int tmp = 0, n = cn[i];
			for (int i = 0; i < n; ++i) tmp = (tmp + qp(k, gcd(i, n))) % P;
			tmp = 1ll * tmp * qp(n, P - 2) % P;
			ans = 1ll * ans * tmp % P;
		}
	}
	printf("%d\n", ans);
	return 0;
}

Submission Info

Compile Error

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

Judge Result