Submission #941711

---

Source Code Expand

#define _USE_MATH_DEFINES
#include <cstdio>
#include <stack>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>

using namespace std;

typedef long long int64;
typedef pair<int, int> ii;
const int MOD = 1e9 + 7;

const int N = 50 + 10;
const int M = 100 + 10;
int dp[N];
vector<int> a[N];
int dfn[N], low[N];
int bcc[N];
int pre[N];

int stamp;
void DFS(int u) {
  static stack<int> S;
  low[u] = dfn[u] = stamp++;
  S.push(u);
  int child = 0;
  for (auto& v : a[u]) {
    if (dfn[v] == 0) {
      ++child;
      pre[v] = u;
      DFS(v);
      low[u] = min(low[u], low[v]);
      if (low[v] >= dfn[u]) {
        while (S.top() != v) {
          bcc[S.top()] = v;
          S.pop();
        }
        bcc[v] = v;
        S.pop();
        // if (u != 0 || child > 1) cut[u] = true;
      }
    } else {
      low[u] = min(low[u], dfn[v]);
    }
  }
}

int64 power_mod(int64 a, int n) {
  int64 ret = 1;
  for (; n; n >>= 1) {
    if (n & 1) ret = ret * a % MOD;
    a = a * a % MOD;
  }
  return ret;
}

int64 inv_mod(int64 a) {
  return power_mod(a, MOD - 2);
}

int C[300][300];
int main() {
  for (int i = 0; i < 300; ++i) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; ++j) {
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
    }
  }
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= i; ++j) {
      dp[i] += power_mod(k, __gcd(i, j)) % MOD;
      dp[i] %= MOD;
    }
    dp[i] = dp[i] * inv_mod(i) % MOD;
    // cout << i << ": " << dp[i] << endl;
  }
  for (int i = 0; i < m; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    --x; --y;
    a[x].push_back(y);
    a[y].push_back(x);
  }
  int ret = 1;
  for (int i = 0; i < n; ++i) {
    if (dfn[i]) continue;
    stamp = 1;
    DFS(i);
  }
  // for (int i = 0; i < n; ++i) {
  //   cout << i << ": " << bcc[i] << endl;
  // }
  for (int i = 0; i < n; ++i) {
    if (bcc[i] != i) continue;
    set<int> A;
    A.insert(pre[i]);
    for (int j = 0; j < n; ++j) {
      if (bcc[j] == i) A.insert(j);
    }
    int cnt = 0;
    for (auto& u : A) {
      for (auto& v : a[u]) {
        if (A.find(v) != A.end()) {
          ++cnt;
        }
      }
    }
    cnt /= 2;
    if (cnt == A.size()) {
      ret = (int64)ret * dp[cnt] % MOD;
    } else {
      ret = (int64)ret * C[cnt + k - 1][cnt] % MOD;
    }
  }
  printf("%d\n", ret);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:82:30: 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:93:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &x, &y);
                          ^

Judge Result