Submission #933463
Source Code Expand
#include <algorithm>
#include <set>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <limits>
#include <memory>
#include <queue>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
#define all(a) (a).begin(), (a).end()
#define sz(a) static_cast<int>((a).size())
#define fillchar(a, x) memset(a, x, sizeof(a))
#define rep(i, a, b) for(int i=int(a); i<=int(b); ++i)
#define irep(i, a, b) for(int i=int(a); i>=int(b); --i)
#define replr(i, a, b) rep(i, a, (b)-1)
#define reprl(i, a, b) irep(i, (b)-1, a)
#define repn(i, n) rep(i, 0, (n)-1)
#define irepn(i, n) irep(i, (n)-1, 0)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef vector<LL> VL;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<string> VS;
template<class T, class S> ostream& operator<<(ostream& os, const pair<T, S>& v) { return os<<"("<<v.first<<", "<<v.second<<")"; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& v) { os<<"["; repn(i, sz(v)) { if(i) os<<", "; os<<v[i]; } return os<<"]"; }
template<class T> bool setmax(T &_a, T _b) { if(_b>_a) { _a=_b; return true; } return false; }
template<class T> bool setmin(T &_a, T _b) { if(_b<_a) { _a=_b; return true; } return false; }
template<class T> T gcd(T _a, T _b) { return _b==0?_a:gcd(_b,_a%_b); }
const LL MOD=LL(1e9)+7;
int main() {
int n, m, k; scanf("%d%d%d", &n,&m,&k);
vector<VI> es(n);
repn(i, m) {
int a, b; scanf("%d%d", &a,&b);
--a, --b;
es[a].pb(b), es[b].pb(a);
}
VI vis(n, 0), dfn(n), low(n);
vector<VPI> comps;
VPI stack;
int label=0;
const function<void(int, int)> dfs=[&](int x, int fa) {
dfn[x]=low[x]=label++;
vis[x]=-1;
for(int y: es[x]) if(y!=fa && vis[y]<=0) {
stack.pb(mp(x, y));
if(vis[y]==0) {
dfs(y, x);
if(low[y]>=dfn[x]) {
VPI comp;
do {
comp.pb(stack.back());
stack.pop_back();
} while(comp.back()!=mp(x, y));
comps.pb(comp);
}
setmin(low[x], low[y]);
} else {
setmin(low[x], dfn[y]);
}
}
vis[x]=1;
};
repn(x, n) if(vis[x]==0) dfs(x, -1);
const int N=210;
static LL pow[N], inv[N], binom[N][N];
const auto power=[&](LL a, LL b) {
LL c=1;
for(; b>0; b>>=1, a=a*a%MOD)
if(b&1) c=c*a%MOD;
return c;
};
pow[0]=1;
rep(i, 1, N-1) pow[i]=(pow[i-1]*k)%MOD;
rep(i, 1, N-1) inv[i]=power(i, MOD-2);
repn(i, N) binom[i][0]=binom[i][i]=1;
rep(i, 1, N-1) rep(j, 1, i-1) binom[i][j]=(binom[i-1][j-1]+binom[i-1][j])%MOD;
LL ans=1;
for(const auto& c: comps) {
if(sz(c)==1) {
(ans*=k)%=MOD;
continue;
}
set<int> s; for(PII p: c) s.insert(p.fi), s.insert(p.se);
//cout<<sz(c)<<" "<<sz(s)<<": "<<c<<" "<<VI(all(s))<<endl;
if(sz(c)==sz(s)) {
LL tmp=0;
rep(i, 1, sz(c)) (tmp+=pow[gcd(i,sz(c))])%=MOD;
(tmp*=inv[sz(c)])%=MOD;
(ans*=tmp)%=MOD;
} else {
(ans*=binom[k+sz(c)-1][sz(c)])%=MOD;
}
}
cout<<ans<<endl;
return 0;
}
Submission Info
Submission Time
2016-10-16 18:53:24+0900
Task
F - Painting Graphs with AtCoDeer
User
fqw
Language
C++14 (GCC 5.4.1)
Score
1300
Code Size
3640 Byte
Status
AC
Exec Time
3 ms
Memory
640 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:47:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int n, m, k; scanf("%d%d%d", &n,&m,&k);
^
./Main.cpp:50:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int a, b; scanf("%d%d", &a,&b);
^
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
640 KB
0_001.txt
AC
3 ms
640 KB
0_002.txt
AC
3 ms
640 KB
1_003.txt
AC
3 ms
640 KB
1_004.txt
AC
3 ms
640 KB
1_005.txt
AC
3 ms
640 KB
1_006.txt
AC
3 ms
640 KB
1_007.txt
AC
3 ms
640 KB
1_008.txt
AC
3 ms
640 KB
1_009.txt
AC
3 ms
640 KB
1_010.txt
AC
3 ms
640 KB
1_011.txt
AC
3 ms
640 KB
1_012.txt
AC
3 ms
640 KB
1_013.txt
AC
3 ms
640 KB
1_014.txt
AC
3 ms
640 KB
1_015.txt
AC
3 ms
640 KB
1_016.txt
AC
3 ms
640 KB
1_017.txt
AC
3 ms
640 KB
1_018.txt
AC
3 ms
640 KB
1_019.txt
AC
3 ms
640 KB
1_020.txt
AC
3 ms
640 KB
1_021.txt
AC
3 ms
640 KB
1_022.txt
AC
3 ms
640 KB
1_023.txt
AC
3 ms
640 KB
1_024.txt
AC
3 ms
640 KB
1_025.txt
AC
3 ms
640 KB
1_026.txt
AC
3 ms
640 KB
1_027.txt
AC
3 ms
640 KB
1_028.txt
AC
3 ms
640 KB
1_029.txt
AC
3 ms
640 KB
1_030.txt
AC
3 ms
640 KB
1_031.txt
AC
3 ms
640 KB
1_032.txt
AC
3 ms
640 KB
1_033.txt
AC
3 ms
640 KB
1_034.txt
AC
3 ms
640 KB
1_035.txt
AC
3 ms
640 KB
1_036.txt
AC
3 ms
640 KB
1_037.txt
AC
3 ms
640 KB
1_038.txt
AC
3 ms
640 KB
1_039.txt
AC
3 ms
640 KB
1_040.txt
AC
3 ms
640 KB
1_041.txt
AC
3 ms
640 KB
1_042.txt
AC
3 ms
640 KB
1_043.txt
AC
3 ms
640 KB
1_044.txt
AC
3 ms
640 KB
1_045.txt
AC
3 ms
640 KB
1_046.txt
AC
3 ms
640 KB
1_047.txt
AC
3 ms
640 KB
1_048.txt
AC
3 ms
640 KB
1_049.txt
AC
3 ms
640 KB
1_050.txt
AC
3 ms
640 KB
1_051.txt
AC
3 ms
640 KB
1_052.txt
AC
3 ms
640 KB
1_053.txt
AC
3 ms
640 KB
1_054.txt
AC
3 ms
640 KB
1_055.txt
AC
3 ms
640 KB
1_056.txt
AC
3 ms
640 KB
1_057.txt
AC
3 ms
640 KB
1_058.txt
AC
3 ms
640 KB
1_059.txt
AC
3 ms
640 KB
1_060.txt
AC
3 ms
640 KB
1_061.txt
AC
3 ms
640 KB
1_062.txt
AC
3 ms
640 KB
1_063.txt
AC
3 ms
640 KB