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

Submission Time
Task F - Painting Graphs with AtCoDeer
User chaemon
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 8065 Byte
Status AC
Exec Time 3 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1300 / 1300
Status
AC × 3
AC × 64
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