Submission #1635225

---

Source Code Expand

// Painting Graphs with AtCoDeer
// * frank_c1
// * 2017 / 09 / 30

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

const int maxn = 205;
const int mo = (int)(1e9) + 7;
int C[maxn][maxn], pw[maxn], inv[maxn];
int dfn[maxn], low[maxn], top;
vector<int> nxt[maxn];
pii stk[maxn];
int K, idx;
LL ret = 1;

void chk(int u, int v) {
	int cnt = 0, s = stk[top].second, succ = 1, lst = 0;
	while (top && stk[top] != make_pair(u, v)) {
		++cnt; if (lst && lst != stk[top].second) succ = 0; lst = stk[top].first; --top;
	} 
	if (stk[top] == make_pair(u, v)) {
		++cnt; if (lst && lst != stk[top].second) succ = 0; lst = stk[top].first; --top;
	} 
	if (!cnt) return;
	else if (cnt == 1) ret = ret * K % mo;
	else if (succ && lst == s) {
		LL buf = 0;
		for (int i = 1; i <= cnt; ++i) (buf += pw[__gcd(cnt, i)]) %= mo; buf = buf * inv[cnt] % mo;
		ret = ret * buf % mo;
	} else ret = ret * C[cnt + K - 1][K - 1] % mo;
}

void dfs(int x, int f) {
	dfn[x] = low[x] = ++idx;
	for (int i = 0; i < (int)nxt[x].size(); ++i) if (nxt[x][i] != f) {
		int v = nxt[x][i];
		stk[++top] = make_pair(x, v);
		if (!dfn[v]) {
			dfs(v, x); low[x] = min(low[x], low[v]);
			if (low[v] >= dfn[x]) chk(x, v);
 		} else if (dfn[v] < dfn[x]) {
 			low[x] = min(low[x], dfn[v]);
 		} else --top;
	} 
}

int main() {
	int n, m;
	scanf("%d%d%d", &n, &m, &K);
	int mx = m + K;
	for (int i = 0; i <= mx; ++i) C[i][0] = 1;
	for (int i = 1; i <= mx; ++i) for (int j = 1; j <= i; ++j) {
		C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; if (C[i][j] >= mo) C[i][j] -= mo;
	} 
	pw[0] = inv[0] = 1; inv[1] = 1;
	for (int i = 1; i <= m; ++i) pw[i] = 1LL * pw[i - 1] * K % mo;
	for (int i = 2; i <= m; ++i) inv[i] = 1LL * (mo - (mo / i)) * inv[mo % i] % mo;
	for (int i = 1; i <= m; ++i) {
		int u, v; scanf("%d%d", &u, &v); nxt[u].push_back(v); nxt[v].push_back(u);
	}
	for (int i = 1; i <= n; ++i) if (!dfn[i]) dfs(i, 0);
	return printf("%lld\n", ret), 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:52: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:62:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d%d", &u, &v); nxt[u].push_back(v); nxt[v].push_back(u);
                                  ^

Judge Result