Submission #1007800
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define dump(...) cout<<"# "<<#__VA_ARGS__<<'='<<(__VA_ARGS__)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple
using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vd=vector<double>;
using vvd=vector<vd>;
using vs=vector<string>;
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename Tuple>
void print_tuple(ostream&,const Tuple&){}
template<typename Car,typename... Cdr,typename Tuple>
void print_tuple(ostream& os,const Tuple& t){
print_tuple<Cdr...>(os,t);
os<<(sizeof...(Cdr)?",":"")<<get<sizeof...(Cdr)>(t);
}
template<typename... Args>
ostream& operator<<(ostream& os,const tuple<Args...>& t){
print_tuple<Args...>(os<<'(',t);
return os<<')';
}
template<typename Ch,typename Tr,typename C>
basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){
os<<'[';
for(auto i=begin(c);i!=end(c);++i)
os<<(i==begin(c)?"":" ")<<*i;
return os<<']';
}
constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;
using Edge=tuple<int,int>;
int dfs(const vvi& g,int p,int u,vi& ord,vi& low,vector<Edge>& s,vector<vector<Edge>>& bcs)
{
int cnt=1;
for(int v:g[u]) if(v!=p){
if(ord[v]<ord[u])
s.emplace_back(u,v);
if(ord[v]==-1){
ord[v]=low[v]=ord[u]+cnt;
cnt+=dfs(g,u,v,ord,low,s,bcs);
low[u]=min(low[u],low[v]);
if(ord[u]<=low[v]){
bcs.emplace_back();
for(;;){
Edge e=s.back(); s.pop_back();
bcs.back().push_back(e);
if(e==Edge(u,v)) break;
}
}
}
else
low[u]=min(low[u],ord[v]);
}
return cnt;
}
vector<vector<Edge>> biconnected_components(const vvi& g)
{
int n=g.size();
vi ord(n,-1),low(n);
vector<Edge> s;
vector<vector<Edge>> bcs;
rep(i,n) if(ord[i]==-1){
ord[i]=low[i]=0;
dfs(g,-1,i,ord,low,s,bcs);
}
return bcs;
}
int ModPow(int a,int r,int m)
{
int x=1;
for(;r;r>>=1){
if(r&1) x=(ll)x*a%m;
a=(ll)a*a%m;
}
return x;
}
int ModInverse(int a,int m)
{
int x=1;
for(int b=m,u=0;b;){
ll t=a/b;
swap(a-=b*t,b);
swap(x-=u*t,u);
}
return (x+m)%m;
}
int ModMul(int a,int b,int m)
{
return (ll)a*b%m;
}
int ModDiv(int a,int b,int m)
{
return ModMul(a,ModInverse(b,m),m);
}
int Choose(int n,int r,int m)
{
int res=1;
rep(i,r) res=ModMul(res,n-i,m);
rep(i,r) res=ModDiv(res,i+1,m);
return res;
}
int main()
{
for(int n,m,k;cin>>n>>m>>k&&n|m|k;){
vvi g(n);
rep(i,m){
int u,v; cin>>u>>v; u--,v--;
g[u].push_back(v);
g[v].push_back(u);
}
ll res=1;
for(auto bc:biconnected_components(g)){
int m=bc.size();
if(m==1)
(res*=k)%=MOD;
else{
set<int> vs;
for(Edge e:bc){
vs.insert(get<0>(e));
vs.insert(get<1>(e));
}
if(vs.size()==m){ // cycle
ll tmp=0;
rep(i,m)
(tmp+=ModPow(k,__gcd(m,i),MOD))%=MOD;
(res*=ModDiv(tmp,m,MOD))%=MOD;
}
else{
(res*=Choose(k+m-1,m,MOD))%=MOD;
}
}
}
cout<<res<<endl;
}
}
Submission Info
Submission Time |
|
Task |
F - Painting Graphs with AtCoDeer |
User |
lyoz |
Language |
C++14 (GCC 5.4.1) |
Score |
1300 |
Code Size |
3448 Byte |
Status |
AC |
Exec Time |
3 ms |
Memory |
256 KB |
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 |
3 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 |