Submission #932135
Source Code Expand
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,P> P1;
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))
const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
struct UF{
int par[102],r[102],siz[102];
void init(){
rep(i,102){
par[i] = i;
r[i] = 0;
siz[i] = 1;
}
}
int find(int x){
if(par[x] == x)return x;
return par[x] = find(par[x]);
}
bool same(int x,int y){
return find(x) == find(y);
}
void unit(int x,int y){
if(same(x,y))return;
x = find(x);
y = find(y);
if(r[x] < r[y]){
par[x] = y;
siz[y] += siz[x];
}
else {
par[y] = x;
siz[x] += siz[y];
if(r[x] == r[y]){
r[x] ++;
}
}
}
}uf;
const ll M = 1000000007;
ll modpow(ll x,ll k){
if(k == 0)return 1;
ll ret = modpow(x,k/2);
ret *= ret; ret %= M;
if(k%2 == 1){ ret *= x; ret %= M; }
return ret;
}
ll inverse(ll x){
return modpow(x,M-2);
}
ll C(ll n,ll k){
ll ret = 1;
rep1(i,k){
ret *= n+1-i; ret %= M;
ret *= inverse(i); ret %= M;
}
return ret;
}
vector<P> G[102];
int color[102];
bool dfs(int v,int c){
if(color[v] == c)return true;
if(color[v] == 0)return true;
if(color[v] != -1)return false;
color[v] = c;
rep(i,G[v].size()){
if(!dfs(G[v][i].fr,c))return false;;
}
return true;
}
bool same(int s,int t,int u){
rep(i,102)color[i] = -1;
color[s] = 0;
dfs(t,1);
return dfs(u,2);
}
int main(){
ll n,m,k;
ll a[102],b[102];
scanf("%lld%lld%lld",&n,&m,&k);
rep(i,m){
scanf("%lld%lld",&a[i],&b[i]);
G[a[i]].pb(P(b[i],i));
G[b[i]].pb(P(a[i],i));
}
ll f[52],g[52];
rep1(i,n){
f[i] = modpow(k,i);
rep1(d,i-1){
if(i%d == 0)f[i] += M-f[d];
}
f[i] %= M;
g[i] = 0;
rep1(d,i){
if(i%d == 0)g[i] += f[d]*inverse(d);
}
g[i] %= M;
//cout << i << ":" << f[i] << " " << g[i] << endl;
}
uf.init();
rep1(i,n){
for(int j = 0 ; j < G[i].size() ; j ++){
for(int t = j+1 ; t < G[i].size() ; t ++){
if(!same(i,G[i][j].fr,G[i][t].fr)){
uf.unit(G[i][j].sc,G[i][t].sc);
//printf("%d %lld %lld\n",i,G[i][j].fr,G[i][j].sc);
//printf("%lld %lld\n",G[i][j].sc,G[i][t].sc);
}
}
}
}
/*rep(i,m){
cout << i << ":" << uf.find(i) << endl;
}*/
ll ret = 1;
ll used = 0;
rep(i,m){
if(uf.find(i) != i)continue;
if(uf.siz[i] == 1){
ret *= k;
ret %= M;
continue;
}
set<ll> cnt;
rep(j,m){
if(uf.same(i,j)){
//cout << i << " " << j << endl;
//cout << uf.find(i) << " " << uf.find(j) << endl;
cnt.insert(a[j]);
cnt.insert(b[j]);
}
}
if(cnt.size() == uf.siz[i])ret *= g[cnt.size()];
else ret *= C(k+uf.siz[i]-1,k-1);
used += cnt.size();
ret %= M;
//cout << i << ":" << cnt.size() << " " << ret << endl;
}
//rep(i,m-used){ ret *= k; ret %= M; }
cout << ret << endl;
}
Submission Info
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:116:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld",&n,&m,&k);
^
./Main.cpp:118:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&a[i],&b[i]);
^
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 |
4 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 |
4 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 |
4 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 |
4 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 |