Submission #931522

---

Source Code Expand

// In the name of God

#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>

using namespace std;
#define int long long
const int N = (int) 205, mod = (int) 1e9 + 7;
int dp[N][N], cnt[N], par[N], cut[N], comb[N][N], h[N], mark[N], s[N], t[N], low[N];
vector<int> ecp[N], comp[N], ver, adj[N], ed;
stack<int> st;
/*
   int dfs(int v, int p = -1, int ep = -1) {
   if (mark[v]++) return h[v];
   ver.push_back(v);
   h[v] = (p == -1? 0: h[p] + 1);
   int res = h[v];
   for (int e : adj[v]) {
   if (e != ep) {
   int u = s[e] ^ t[e] ^ v;
   res = min(res, dfs(u, v, e));
   }
   }
   if (ep != -1 && res == h[v]) {
   cut[ep] = 1;
   }
   return res;
   }*/
int dfs_bcc(int v, int p = -1) {
    if (mark[v]++) {
        return h[v];
    }
    h[v] = (p == -1? 0: h[p] + 1);
    low[v] = h[v];
    st.push(v);
    for (int e : adj[v])
        low[v] = min(low[v], dfs_bcc(s[e] ^ t[e] ^ v, v));
    if (h[v] - 1 == low[v]) {
        while (st.top() != v) {
            int u = st.top(); st.pop();
            comp[u].push_back(v);
        }
        comp[v].push_back(v);
        st.pop();
        comp[p].push_back(v);
    }
    return low[v];
}
int marke[N];
int pw(int a, int b) { return b != 0? pw(a * 1ll * a % mod, b >> 1) * 1ll * (b & 1? a : 1) % mod: 1; }
int g[N], n, m, k;
int cycle(int x) {
    long long res = 0;
    memset(g, 0, sizeof g);
    for (int d = x; d >= 1; --d) if (x % d == 0) {
        g[d] = pw(k, x / d);
        for (int p = x; p > d; --p) if (p % d == 0) {
            g[d] = (g[d] - g[p] + mod) % mod;
        }
    }
    for (int d = 1; d <= x; ++d) if (x % d == 0)
        res = (res + g[d] * 1ll * pw(x / d, mod - 2)) % mod;
    return res;
}
int find(int x) { return x == par[x]? x: par[x] = find(par[x]); }
void unite(int u, int v) { par[find(u)] = find(v); }
int cnte[N], cntv[N];
int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j <= i; ++j) {
            comb[i][j] = 1;
            if (i != j && j > 0) {
                comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % mod;
            }
        }   
    for (int i = 0; i < m; ++i) {
        int &u = s[i], &v = t[i];
        cin >> u >> v;
        --u, --v;
        adj[u].push_back(i);
        adj[v].push_back(i);
    }
    long long res = 1;
    for (int v = 0; v < n; ++v) if (!mark[v]) {
        dfs_bcc(v);
    }
    for (int e0 = 0; e0 < m; ++e0) {
        int flag = 1;
        for (int a : comp[s[e0]]) {
            for (int b : comp[t[e0]])
                if (a == b) {
                    ecp[a].push_back(e0);
                    flag = 0;
                    break;
                }
            if (!flag) break;
        }
    }
    for (int v = 0; v < n + n; ++v) if (ecp[v].size()) {
        vector<int> vv;
        for (int e : ecp[v]) {
            vv.push_back(s[e]);
            vv.push_back(t[e]);
        }
        sort(vv.begin(), vv.end());
        vv.resize(unique(vv.begin(), vv.end()) - vv.begin());
        int vc = vv.size();
        int ec = ecp[v].size();
        if (ec == vc) {
            res = res * 1ll * cycle(vc) % mod;
        } else
            res = res * 1ll * comb[ec + k - 1][k - 1] % mod;
    }
    for (int e = 0; e < m; ++e) if (cut[e]) {
        res = res * 1ll * k % mod;
    }
    cout << res << endl;
}

Submission Info

Judge Result