Submission #937375

---

Source Code Expand

#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define maxv 114
stack<pint> S;//辺を追加するスタック
vector<vector<pint> > bc;//二重頂点成分
vector<int> art;//関節点集合
vector<int> gr[maxv];//隣接リストで持つグラフ
int low[maxv],num[maxv];//numは行きがけ順。必ず-1で初期化すること
int it=0;//行きがけ順の頂点番号
int zi[114];

void dfs(int v,int u){
	low[v]=num[v]=it++;
	rep(i,gr[v].size()){
		int w=gr[v][i];
		if(w==u) continue;
		if(num[w]<num[v]) S.push(mp(v,w));//二重頂点成分のために辺をスタックに追加
		if(num[w]<0){
			dfs(w,v);
			low[v]=min(low[v],low[w]);
			if((num[v]==0 && num[w]>1) || (num[v]>0 && low[w]>=num[v])) art.pb(v);//関節点をartに追加
			if(low[w]>=num[v]){//二重頂点成分をbcompに追加
				vector<pint> ed;
				while(1){
					pint p=S.top();S.pop();ed.pb(p);if(p.fi==v && p.se==w) break;
				}
				if(ed.size()>0) bc.pb(ed);
			}
		}
		else low[v]=min(low[v],num[w]);
	}
}

lint mo=1000000007;
lint co[222][222];
lint extgcd(lint a, lint b, lint &x, lint &y) {
  lint g = a; x = 1; y = 0;
  if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
  return g;
}
lint invMod(lint a, lint m) {
  lint x, y;
  if (extgcd(a, m, x, y) == 1) return (x + m) % m;return 0;
}
int gcd( int m, int n )
{
	int a=max(m,n),b=min(m,n);
	if(m==0) return n;if(n==0) return m;
	if(a%b==0) return b;
	return gcd(b,a-b*(a/b));
}
lint zyo(lint x,lint y){
    lint ret=1,a=x;
    while(y>0){
    	if(y%2==1) ret=(ret*a)%mo;
    	a=(a*a)%mo;y/=2;
    }
    return ret;
}
lint cal(int a,lint K){
	lint out=0;
	REP(i,1,a+1){
		out+=zyo(K,gcd(a,i));
		out%=mo;
	}
	out*=invMod(a,mo);
	//cout<<out%mo<<endl;
	return out%mo;
}
int main()
{
	rep(i,214){
		co[i][0]=co[i][i]=1;
		REP(j,1,i) co[i][j]=(co[i-1][j-1]+co[i-1][j])%mo;
	}
	
	int n,m,K,a,b;lint out=1;
	cin>>n>>m>>K;
	memset(zi,0,sizeof(zi));
	rep(i,m){
		cin>>a>>b;a--;b--;
		gr[a].pb(b);gr[b].pb(a);
		zi[a]++;zi[b]++;
	}
	memset(num,-1,sizeof(num));//初期化を忘れない！！！！
	rep(i,n){
		if(num[i]>=0 || zi[i]<1) continue;
		dfs(i,-1);
	}
	
	/*rep(i,art.size()) cout<<art[i]<<endl;cout<<endl;
	rep(i,bc.size()){
		rep(j,bc[i].size()) cout<<bc[i][j].fi<<' '<<bc[i][j].se<<endl;cout<<endl;
	}*/
	//cout<<(co[57][10]*48*48)%mo<<endl;
	
	rep(i,bc.size()){
		int N=bc[i].size();
		if(N<1) continue;
		set<int> s;
		rep(j,N) s.insert(bc[i][j].fi),s.insert(bc[i][j].se);
		int e=s.size();
		//cout<<e<<' '<<N<<endl;
		if(e==N) out*=cal(e,K);
		else if(e==N+1) out*=zyo(K,N);
		else out*=co[N+K-1][N];
		out%=mo;
	}
	cout<<out%mo<<endl;
}

Submission Info

Judge Result