Submission #948415

---

Source Code Expand

#include <bits/stdc++.h>

/* -------------------------------- Template -------------------------------- */

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

template<typename T> T inf() { assert(false); }
template<> constexpr int inf<int>() { return 1e9; }
template<> constexpr ll inf<ll>() { return 1e18; }
template<> constexpr ld inf<ld>() { return 1e30; }

struct yes_no : numpunct<char> {
  string_type do_truename()  const { return "Yes"; }
  string_type do_falsename() const { return "No"; }
};

/* -------------------------------- Library -------------------------------- */

struct Edge{
  int src, dest;
  bool operator < (const Edge &rhs) const {
    return make_pair(src, dest) < make_pair(rhs.src, rhs.dest);
  }
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

set<int> art;
vector<set<Edge> > connect;
vector<Edge> st;
vector<int> order, low;
int cnt;

void artDfs(const Graph &g, int from, int parent) {
  low[from] = order[from] = cnt++;
  for (Edge e : g[from]) {
    int to = e.dest;
    if (to != parent && order[to] < order[from]) st.push_back(e);
    if (order[to] == -1) {
      artDfs(g, to, from);
      low[from] = min(low[from], low[to]);
      if ((order[from] == 0 && order[to] != 1) || (order[from] != 0 && low[to] >= order[from]))
        art.insert(from);
      if (low[to] >= order[from]) {
        connect.push_back(set<Edge>());
        while (true) {
          Edge edge = st.back();
          st.pop_back();
          connect.back().insert(edge);
          if (edge.src == from && edge.dest == to) break;
        }
      }
    }
    else {
      low[from] = min(low[from], order[to]);
    }
  }
}

set<int> articulationPoints(const Graph &g) {
  const int n = g.size();
  art.clear(); connect.clear(); st.clear();
  order.assign(n, -1); low.assign(n, -1);
  for (int i = 0; i < n; i++) {
    if (order[i] != -1) continue;
    cnt = 0;
    artDfs(g, i, i);
  }
  return art;
}

const int mod = 1000000007;

struct Mod {
  int n;
  Mod () : n(0) {;}
  Mod (int m) : n(m) {
    if (n >= mod) n %= mod;
    else if (n < 0) n = (n % mod + mod) % mod;
  }
  operator int() { return n; }
};

bool operator==(Mod a, Mod b) { return a.n == b.n; }
Mod operator+=(Mod &a, Mod b) { a.n += b.n; if (a.n >= mod) a.n -= mod; return a; }
Mod operator-=(Mod &a, Mod b) { a.n -= b.n; if (a.n < 0) a.n += mod; return a; }
Mod operator*=(Mod &a, Mod b) { a.n = ((long long)a.n * b.n) % mod; return a; }
Mod operator+(Mod a, Mod b) { return a += b; }
Mod operator-(Mod a, Mod b) { return a -= b; }
Mod operator*(Mod a, Mod b) { return a *= b; }
Mod operator^(Mod a, int n) {
  if (n == 0) return Mod(1);
  Mod res = (a * a) ^ (n / 2);
  if (n % 2) res = res * a;
  return res;
}

ll inv(ll a, ll p) {
  return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
Mod operator/(Mod a, Mod b) { return a * Mod(inv(b, mod)); }

#define MAX_N 1024000

Mod fact[MAX_N], factinv[MAX_N];
void init() {
  fact[0] = Mod(1); factinv[0] = 1;
  REP(i,MAX_N-1) {
    fact[i+1] = fact[i] * Mod(i+1);
    factinv[i+1] = factinv[i] / Mod(i+1);
  }
}
Mod comb(int a, int b) {
  return fact[a] * factinv[b] * factinv[a-b];
}

/* ---------------------------------- Main ---------------------------------- */

int main() {
  locale loc(locale(), new yes_no);
  cout << boolalpha;
  cout.imbue(loc);
  init();

  int N, M, K;
  cin >> N >> M >> K;
  Graph g(N);
  REP(i,M) {
    int a, b; cin >> a >> b; --a; --b;
    g[a].push_back((Edge){a, b});
    g[b].push_back((Edge){b, a});
  }
  articulationPoints(g);
  Mod res = 1;
  for (auto es: connect) {
    vector<int> vs;
    for (auto e: es) {
      vs.push_back(e.src);
      vs.push_back(e.dest);
    }
    sort(ALL(vs));
    auto it = unique(ALL(vs));
    int n = it - begin(vs);
    int m = es.size();
    if (n != m) {
      res *= comb(K - 1 + m, m);
      continue;
    }
    Mod sum = 0;
    for (int i = 1; i <= n; ++i) {
      int g = __gcd(i, n);
      sum += Mod(K) ^ g;
    }
    res *= sum / Mod(n);
  }
  cout << res << endl;
  return 0;
}

Submission Info

Judge Result