Submission #1049767
Source Code Expand
// #includes {{{
#include <bits/stdc++.h>
using namespace std;
// }}}
// pre-written code {{{
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define RREP(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i)
#define LET(x,a) __typeof(a) x(a)
//#define IFOR(i,it,c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();++it,++i)
#define ALL(c) (c).begin(), (c).end()
#define MP make_pair
#define EXIST(e,s) ((s).find(e)!=(s).end())
#define RESET(a) memset((a),0,sizeof(a))
#define SET(a) memset((a),-1,sizeof(a))
#define PB push_back
#define DEC(it,command) __typeof(command) it=command
//debug
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define debug2(x) cerr << #x << " = [";REP(__ind,(x).size()){cerr << (x)[__ind] << ", ";}cerr << "] (L" << __LINE__ << ")" << endl;
const int INF=0x3f3f3f3f;
typedef long long Int;
typedef unsigned long long uInt;
typedef long double rn;
typedef pair<int,int> pii;
/*
#ifdef MYDEBUG
#include"debug.h"
#include"print.h"
#endif
*/
// }}}
//{{{ Graph
typedef int Weight;
struct Edge {
int src, dst, rev;
Weight weight;
Edge(int src, int dst, Weight weight=1,int rev=-1) :
src(src), dst(dst), weight(weight), rev(rev) { }
};
bool operator < (const Edge &e, const Edge &f) {
return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
//add bi-directional edge
void addBiEdge(Graph &g,int from ,int to, Weight w=1){
while(g.size()<max(from,to)+1)g.push_back(Edges());
g[from].push_back(Edge(from,to,w,g[to].size()));
g[to].push_back(Edge(to,from,w,g[from].size()-1));
}
//add directional edge
void addEdge(Graph &g,int from ,int to, Weight w=1){
while(g.size()<from+1)g.push_back(Edges());
g[from].push_back(Edge(from,to,w));
}
#ifdef DEBUG
#include"graph/graphviz.h"
#endif
//}}}
#define BCOMP
//{{{ articulationPoint(Graph,vector<int>,vector<Edgeset>)
struct UndirectionalCompare {
bool operator() (const Edge& e, const Edge& f) const {
if (min(e.src,e.dst) != min(f.src,f.dst))
return min(e.src,e.dst) < min(f.src,f.dst);
return max(e.src,e.dst) < max(f.src,f.dst);
}
};
#ifdef BCOMP
typedef set<Edge, UndirectionalCompare> Edgeset;
void visit(const Graph &g, int v, int u,
vector<int>& art, vector<Edgeset>& bcomp,
stack<Edge>& S, vector<int>& num, vector<int>& low, int& time)
#else
void visit(const Graph &g, int v, int u,
vector<int>& art,
stack<Edge>& S, vector<int>& num, vector<int>& low, int& time)
#endif
{
low[v] = num[v] = ++time;
bool articular=false;
FOR(e, g[v]) {
int w = e->dst;
if (num[w] < num[v]) S.push(*e); // for bcomps
if (num[w] == 0) {
#ifdef BCOMP
visit(g, w, v, art, bcomp, S, num, low, time);
#else
visit(g, w, v, art, S, num, low, time);
#endif
low[v] = min(low[v], low[w]);
if ((num[v] == 1 && num[w] != 2) || // for arts
(num[v] != 1 && low[w] >= num[v]))articular=true;
if (low[w] >= num[v]) { // for bcomps
#ifdef BCOMP
bcomp.push_back(Edgeset());
#endif
while (1) {
Edge f = S.top(); S.pop();
#ifdef BCOMP
bcomp.back().insert(f);
#endif
if (f.src == v && f.dst == w) break;
}
}
} else low[v] = min(low[v], num[w]);
}
if(articular)art.push_back(v);
}
#ifdef BCOMP
void articulationPoint(const Graph& g, vector<int>& art, vector<Edgeset>& bcomp) {
#else
void articulationPoint(const Graph& g, vector<int>& art) {
#endif
const int n = g.size();
vector<int> low(n), num(n);
stack<Edge> S;
REP(u, n) if (num[u] == 0) {
int time = 0;
#ifdef BCOMP
visit(g, u, -1, art, bcomp, S, num, low, time);
#else
visit(g, u, -1, art, S, num, low, time);
#endif
}
}
//}}}
//{{{ gcd and inverse
#define __GCD_H
Int gcd(Int a, Int b) {
return b != 0 ? gcd(b, a % b) : a;
}
Int lcm(Int a, Int b) {
return a / gcd(a, b) *b;
}
// a x + b y = gcd(a, b)
Int extgcd(Int a, Int b, Int &x, Int &y) {
Int g = a; x = 1; y = 0;
if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
return g;
}
/*
Int invMod(Int a, Int m) {
Int x, y;
if (extgcd(a, m, x, y) == 1) return (x + m) % m;
else return 0; // unsolvable
}
*/
inline Int invMod(Int a, Int m){
Int b = m, u = 1, v = 0;
while (b) {
Int t = a / b;
swap(a -= t * b, b);
swap(u -= t * v, v);
}
return (u % m + m) % m;
}
//}}}
const int mod = 1000000007;
//{{{ modular algebra
struct Num{
int v;
Num(int n):v(n){}
Num(){}
operator int() const {return v;}
operator long long() const {return v;}
void operator =(int n){v=n;}
template<class T>
inline void operator *=(const T &a) {
v = (v*(long long)a)%mod;
}
template<class T>
inline Num operator *(const T &a) {
Num n(*this);n*=a;
return n;
}
template<class T>
inline void operator+=(const T &a){
v+=(int)a;
if(v>=mod)v-=mod;
// assert(0<=v and v<mod);
}
template<class T>
inline Num operator+(const T &a){
Num n(*this);n+=a;
return n;
}
inline Num operator -(){
if(v==0)return v;
else return Num(mod-v);
}
template<class T>
inline void operator -=(const T &a){
v-=(int)a;
if(v<0)v+=mod;
}
template<class T>
inline Num operator -(const T &a){
Num n(*this);n-=a;
return n;
}
#ifdef __GCD_H
inline Num inv(){
return invMod(this->v,mod);
}
template<class T>
inline void operator /=(const T &a){
(*this)*=invMod((int)a,mod);
}
template<class T>
inline Num operator /(const T &a){
Num n(*this);n/=a;
return n;
}
#endif
};
//}}}
//{{{ fact, binom, multinom
inline Num fact(int n,const int &mod = mod){
static vector<Num> __fact(1,1);
while(n>=__fact.size())__fact.push_back(__fact.back()*__fact.size());
return __fact[n];
}
inline Num binom(int n,int r){
if(n<0 or r<0 or n<r)return 0;
return fact(n)/(fact(r)*fact(n-r));
}
inline Num multinom(const vector<int> &v){
Num num(fact(accumulate(ALL(v),0))), denom(1);
REP(i,v.size())denom*=fact(v[i]);
return num/denom;
}
//}}}
//{{{ pow
/* (x^k)%m */
inline Num pow(Num x, int k){
if(k==0) return 1;
Num res(pow(x,k/2));
res*=res;
if(k%2)res*=x;
return res;
}
//}}}
int N,M,K;
Num dp0[55];
Num circle(int L){
Num ans = 0;
for(int i=0;i<L;i++){
ans+=pow((Num)K,gcd(L,i));
}
ans/=L;
/*
Num ans = 0;
for(int d=1;d<=L;d++){
if(L%d!=0)continue;
Num t = pow((Num)K,d);
for(int d2=1;d2<d;d2++){
if(d%d2!=0)continue;
t -= dp0[d2]*d2;
}
dp0[d] = t/d;
ans+=dp0[d];
}
*/
return ans;
}
Num dp1[110][55];
Num circle_alpha(int L){
return binom(K+L-1,L);
// cerr<<"circle_alpha "<<L<<endl;
for(int i=0;i<=K;i++)for(int j=0;j<=L;j++)dp1[i][j] = 0;
// memset(dp1,0,sizeof(dp1));
dp1[0][0] = 1;
REP(i,K){
for(int j=0;j<=L;j++){
for(int k=0;j+k<=L;k++){
dp1[i+1][j+k]+=dp1[i][j];
}
}
}
return dp1[K][L];
}
int main(){
cin>>N>>M>>K;
Graph g(N);
REP(i,M){
int a,b;
cin>>a>>b;
a--;b--;
addBiEdge(g,a,b);
}
vector<int> art;
vector<Edgeset> es;
articulationPoint(g,art,es);
Num ans = 1;
REP(i,es.size()){
set<int> ps;
FOR(it,es[i]){
ps.insert(it->src);
ps.insert(it->dst);
}
if(ps.size()<es[i].size()){//circle + alpha
// cerr<<"circle+alpha: "<<es[i].size()<<endl;
ans*=circle_alpha(es[i].size());
}else if(ps.size()==es[i].size()){//circle
// cerr<<"circle: "<<es[i].size()<<endl;
ans*=circle(es[i].size());
}else{//tree
// cerr<<"tree: "<<es[i].size()<<endl;
ans*=pow((Num)K,es[i].size());
// cerr<<(int)pow((Num)K,es[i].size())<<endl;
}
}
cout<<(int)ans<<endl;
return 0;
}
Submission Info
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1300 / 1300 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_000.txt, 0_001.txt, 0_002.txt |
All |
0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt, 1_042.txt, 1_043.txt, 1_044.txt, 1_045.txt, 1_046.txt, 1_047.txt, 1_048.txt, 1_049.txt, 1_050.txt, 1_051.txt, 1_052.txt, 1_053.txt, 1_054.txt, 1_055.txt, 1_056.txt, 1_057.txt, 1_058.txt, 1_059.txt, 1_060.txt, 1_061.txt, 1_062.txt, 1_063.txt |
Case Name |
Status |
Exec Time |
Memory |
0_000.txt |
AC |
3 ms |
256 KB |
0_001.txt |
AC |
3 ms |
256 KB |
0_002.txt |
AC |
3 ms |
256 KB |
1_003.txt |
AC |
3 ms |
256 KB |
1_004.txt |
AC |
3 ms |
256 KB |
1_005.txt |
AC |
3 ms |
256 KB |
1_006.txt |
AC |
3 ms |
256 KB |
1_007.txt |
AC |
3 ms |
256 KB |
1_008.txt |
AC |
3 ms |
256 KB |
1_009.txt |
AC |
3 ms |
256 KB |
1_010.txt |
AC |
3 ms |
256 KB |
1_011.txt |
AC |
3 ms |
256 KB |
1_012.txt |
AC |
3 ms |
256 KB |
1_013.txt |
AC |
3 ms |
256 KB |
1_014.txt |
AC |
3 ms |
256 KB |
1_015.txt |
AC |
3 ms |
256 KB |
1_016.txt |
AC |
3 ms |
256 KB |
1_017.txt |
AC |
3 ms |
256 KB |
1_018.txt |
AC |
3 ms |
256 KB |
1_019.txt |
AC |
3 ms |
256 KB |
1_020.txt |
AC |
3 ms |
256 KB |
1_021.txt |
AC |
3 ms |
256 KB |
1_022.txt |
AC |
3 ms |
256 KB |
1_023.txt |
AC |
3 ms |
256 KB |
1_024.txt |
AC |
3 ms |
256 KB |
1_025.txt |
AC |
3 ms |
256 KB |
1_026.txt |
AC |
3 ms |
256 KB |
1_027.txt |
AC |
3 ms |
256 KB |
1_028.txt |
AC |
3 ms |
256 KB |
1_029.txt |
AC |
3 ms |
256 KB |
1_030.txt |
AC |
3 ms |
256 KB |
1_031.txt |
AC |
3 ms |
256 KB |
1_032.txt |
AC |
3 ms |
256 KB |
1_033.txt |
AC |
3 ms |
256 KB |
1_034.txt |
AC |
3 ms |
256 KB |
1_035.txt |
AC |
3 ms |
256 KB |
1_036.txt |
AC |
3 ms |
256 KB |
1_037.txt |
AC |
3 ms |
256 KB |
1_038.txt |
AC |
3 ms |
256 KB |
1_039.txt |
AC |
3 ms |
256 KB |
1_040.txt |
AC |
2 ms |
256 KB |
1_041.txt |
AC |
3 ms |
256 KB |
1_042.txt |
AC |
3 ms |
256 KB |
1_043.txt |
AC |
3 ms |
256 KB |
1_044.txt |
AC |
3 ms |
256 KB |
1_045.txt |
AC |
3 ms |
256 KB |
1_046.txt |
AC |
3 ms |
256 KB |
1_047.txt |
AC |
3 ms |
256 KB |
1_048.txt |
AC |
3 ms |
256 KB |
1_049.txt |
AC |
3 ms |
256 KB |
1_050.txt |
AC |
3 ms |
256 KB |
1_051.txt |
AC |
3 ms |
256 KB |
1_052.txt |
AC |
3 ms |
256 KB |
1_053.txt |
AC |
3 ms |
256 KB |
1_054.txt |
AC |
3 ms |
256 KB |
1_055.txt |
AC |
3 ms |
256 KB |
1_056.txt |
AC |
3 ms |
256 KB |
1_057.txt |
AC |
3 ms |
256 KB |
1_058.txt |
AC |
3 ms |
256 KB |
1_059.txt |
AC |
3 ms |
256 KB |
1_060.txt |
AC |
3 ms |
256 KB |
1_061.txt |
AC |
3 ms |
256 KB |
1_062.txt |
AC |
3 ms |
256 KB |
1_063.txt |
AC |
3 ms |
256 KB |