Submission #931808

---

Source Code Expand

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;

int G[50][50] = {0};
const int mmod = 1000000007;

	int inv_mod(int a, int b) {
		if (a == 1) return b;
		int div = mmod / a + 1;
		return inv_mod((a * (long long)div) % mmod, (b * (long long)div) % mmod);
	}

vector<int> gnext[1003];
int v[1003],vtime;
int up[1003];

vector<int> bcc[1003];
int bcc_cnt;
int cut_vertex[1003];

pair<int,int> mystack[1003];
int top;

void dfs(int nod, int par) {
    up[nod] = v[nod] = ++vtime;
    for(int i = 0; i < gnext[nod].size(); i++){
        int next = gnext[nod][i];
        if(v[next] == 0) {
            mystack[top++] = make_pair(nod,next);
            dfs(next, nod);
            if(up[next] >= v[nod]) {
                do {
                    bcc[bcc_cnt].push_back(mystack[--top].second);
                } while( mystack[top] != make_pair(nod,next));
                bcc[bcc_cnt ++].push_back(nod);
                cut_vertex[nod] ++;
            }
            up[nod] = min(up[nod], up[next]);
        } else if(next != par)
            up[nod] = min(up[nod], v[next]);
    }
    if(par == -1 && cut_vertex[nod] == 1)
        cut_vertex[nod] = 0;
}

int neck(int k, int n) {
  int res = 0;
  for (int d=1; d<=n; d++) {
    if (n % d) continue;
    int phi = 1;
    for (int e=2; e<d; e++) if (__gcd(e, d) == 1) phi ++;
    for (int i=0; i<n/d; i++)
      phi = (phi * 1LL * k) % mmod;
    res = (res + phi) % mmod;
  }
  return (res * 1LL * inv_mod(n, 1)) % mmod;
}

int main()
{
  int n, m, k;
  cin >> n >> m >> k;

  for (int i=0; i<m; i++) {
    int a, b;
    cin >> a >> b;
    G[a-1][b-1] = G[b-1][a-1] = 1;
    gnext[a-1].push_back(b-1);
    gnext[b-1].push_back(a-1);
  }
  for (int i=0; i<n; i++)
    if (!up[i])
      dfs(i,-1);

//  for (int i=0; i<n; i++) printf("%d\n", cut_vertex[i]);
  int res = 1;
  for (int i=0; i<bcc_cnt; i++) {
    int sz = bcc[i].size();
    int mm = 0;
    for (int j=0; j<sz; j++)
      for (int k=j+1; k<sz; k++)
        mm += G[bcc[i][j]][bcc[i][k]];
//    printf("%d %d => ", sz, mm);
    if (sz - 1 == mm) {
      for (int j = 0; j < mm; j ++) res = (res * 1LL * k) % mmod;
    }
    else if (sz == mm) {
      res = (res * 1LL * neck(k, sz)) % mmod;
    } else {
      for (int i=1; i<=mm; i++) {
        res = (res * 1LL * (k + i - 1)) % mmod;
        res = (res * 1LL * inv_mod(i, 1)) % mmod;
//        printf("%d %d\n", k+i-1, i);
      }
    }
//    printf("%d\n", res);
  }
  cout << res << endl;
}

Submission Info

Judge Result