Submission #932543
Source Code Expand
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#define SIZE 200005
#define MOD 1000000007
using namespace std;
typedef long long int ll;
ll inv[SIZE],fac[SIZE],finv[SIZE];
void make()
{
fac[0]=fac[1]=1;
finv[0]=finv[1]=1;
inv[1]=1;
for(int i=2;i<SIZE;i++)
{
inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
fac[i]=fac[i-1]*(ll) i%MOD;
finv[i]=finv[i-1]*inv[i]%MOD;
}
}
ll C(int a,int b)
{
if(a<b) return 0;
return fac[a]*(finv[b]*finv[a-b]%MOD)%MOD;
}
int gcd(int x,int y)
{
if(x==0) return y;
return gcd(y%x,x);
}
ll mpow(ll m,ll t)
{
if(t==0) return 1;
ll ret=mpow(m*m%MOD,t/2);
if(t%2==1) ret=ret*m%MOD;
return ret;
}
struct UF
{
int par[SIZE],rank[SIZE];
void init(int n)
{
for(int i=0;i<n;i++)
{
par[i]=i;
rank[i]=1;
}
}
int find(int x)
{
if(x==par[x]) return x;
return par[x]=find(par[x]);
}
void unite(int x,int y)
{
x=find(x);
y=find(y);
if(x==y) return;
if(rank[x]<rank[y])
{
par[x]=y;
}
else
{
par[y]=x;
if(rank[x]==rank[y]) rank[x]++;
}
}
bool same(int x,int y)
{
return find(x)==find(y);
}
};
UF uf;
vector <int> memo[SIZE];
int left[SIZE],right[SIZE];
bool now[SIZE];
struct edge
{
int to,id;
edge(int to=0,int id=0):to(to),id(id){}
};
vector <edge> vec[SIZE];
vector <int> can[SIZE];
int low[SIZE],ord[SIZE];
int par[SIZE],back[SIZE];
bool use[SIZE];
int now_id;
int n,m,K;
void dfs(int v,int p,int q)
{
use[v]=true;
par[v]=p;
back[v]=q;
low[v]=ord[v]=now_id++;
for(int i=0;i<vec[v].size();i++)
{
edge e=vec[v][i];
if(e.to!=p)
{
if(!use[e.to])
{
dfs(e.to,v,e.id);
low[v]=min(low[v],low[e.to]);
}
else
{
low[v]=min(low[v],ord[e.to]);
}
}
}
}
void build()
{
for(int i=0;i<n;i++)
{
if(!use[i])
{
dfs(i,-1,-1);
}
}
for(int i=0;i<n;i++)
{
if(par[i]==-1) continue;
for(int j=0;j<vec[i].size();j++)
{
edge e=vec[i][j];
if(e.to!=par[i]&&low[e.to]<=ord[par[i]])
{
can[back[i]].push_back(e.id);
can[e.id].push_back(back[i]);
//printf("* %d %d\n",back[i],e.id);
}
}
}
}
int main()
{
make();
scanf("%d %d %d",&n,&m,&K);
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d %d",&a,&b);a--;b--;
vec[a].push_back(edge(b,i));
vec[b].push_back(edge(a,i));
left[i]=a,right[i]=b;
}
build();
uf.init(m+2);
for(int i=0;i<m;i++)
{
for(int j=0;j<can[i].size();j++)
{
uf.unite(i,can[i][j]);
}
}
for(int i=0;i<m;i++) memo[uf.find(i)].push_back(i);
ll ret=1;
for(int i=0;i<m;i++)
{
if(memo[i].size()==0) continue;
int nd=0,cnt=memo[i].size();
for(int j=0;j<memo[i].size();j++)
{
int p=memo[i][j];
if(!now[left[p]]) nd++;
if(!now[right[p]]) nd++;
now[left[p]]=now[right[p]]=true;
}
for(int j=0;j<memo[i].size();j++)
{
int p=memo[i][j];
now[left[p]]=now[right[p]]=false;
}
//printf("%d %d\n",nd,cnt);
if(cnt==1) ret=ret*(ll) K%MOD;
else
{
if(nd<cnt)
{
ret=ret*C(cnt+K-1,K-1)%MOD;
}
else
{
ll all=0;
for(int j=1;j<=nd;j++)
{
all+=mpow(K,gcd(j,nd));
if(all>=MOD) all-=MOD;
}
all=all*inv[nd]%MOD;
ret=ret*all%MOD;
}
}
}
printf("%lld\n",ret);
return 0;
}
Submission Info
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:146:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&n,&m,&K);
^
./Main.cpp:150:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&a,&b);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 |
24 ms |
19072 KB |
0_001.txt |
AC |
24 ms |
19072 KB |
0_002.txt |
AC |
24 ms |
19072 KB |
1_003.txt |
AC |
24 ms |
19072 KB |
1_004.txt |
AC |
24 ms |
19072 KB |
1_005.txt |
AC |
24 ms |
19072 KB |
1_006.txt |
AC |
24 ms |
19072 KB |
1_007.txt |
AC |
32 ms |
19072 KB |
1_008.txt |
AC |
24 ms |
19072 KB |
1_009.txt |
AC |
24 ms |
19072 KB |
1_010.txt |
AC |
24 ms |
19072 KB |
1_011.txt |
AC |
24 ms |
19072 KB |
1_012.txt |
AC |
25 ms |
19072 KB |
1_013.txt |
AC |
25 ms |
19200 KB |
1_014.txt |
AC |
24 ms |
19072 KB |
1_015.txt |
AC |
25 ms |
19072 KB |
1_016.txt |
AC |
24 ms |
19072 KB |
1_017.txt |
AC |
24 ms |
19072 KB |
1_018.txt |
AC |
24 ms |
19072 KB |
1_019.txt |
AC |
24 ms |
19072 KB |
1_020.txt |
AC |
24 ms |
19072 KB |
1_021.txt |
AC |
25 ms |
19072 KB |
1_022.txt |
AC |
24 ms |
19072 KB |
1_023.txt |
AC |
24 ms |
19072 KB |
1_024.txt |
AC |
24 ms |
19072 KB |
1_025.txt |
AC |
24 ms |
19072 KB |
1_026.txt |
AC |
24 ms |
19072 KB |
1_027.txt |
AC |
24 ms |
19072 KB |
1_028.txt |
AC |
24 ms |
19072 KB |
1_029.txt |
AC |
24 ms |
19072 KB |
1_030.txt |
AC |
24 ms |
19072 KB |
1_031.txt |
AC |
24 ms |
19072 KB |
1_032.txt |
AC |
25 ms |
19072 KB |
1_033.txt |
AC |
24 ms |
19072 KB |
1_034.txt |
AC |
25 ms |
19072 KB |
1_035.txt |
AC |
24 ms |
19072 KB |
1_036.txt |
AC |
24 ms |
19072 KB |
1_037.txt |
AC |
24 ms |
19072 KB |
1_038.txt |
AC |
24 ms |
19072 KB |
1_039.txt |
AC |
24 ms |
19072 KB |
1_040.txt |
AC |
24 ms |
19072 KB |
1_041.txt |
AC |
24 ms |
19072 KB |
1_042.txt |
AC |
24 ms |
19072 KB |
1_043.txt |
AC |
24 ms |
19072 KB |
1_044.txt |
AC |
24 ms |
19072 KB |
1_045.txt |
AC |
24 ms |
19072 KB |
1_046.txt |
AC |
25 ms |
19072 KB |
1_047.txt |
AC |
24 ms |
19072 KB |
1_048.txt |
AC |
24 ms |
19072 KB |
1_049.txt |
AC |
24 ms |
19072 KB |
1_050.txt |
AC |
24 ms |
19072 KB |
1_051.txt |
AC |
24 ms |
19072 KB |
1_052.txt |
AC |
24 ms |
19072 KB |
1_053.txt |
AC |
24 ms |
19072 KB |
1_054.txt |
AC |
24 ms |
19072 KB |
1_055.txt |
AC |
24 ms |
19072 KB |
1_056.txt |
AC |
24 ms |
19072 KB |
1_057.txt |
AC |
24 ms |
19072 KB |
1_058.txt |
AC |
24 ms |
19072 KB |
1_059.txt |
AC |
24 ms |
19072 KB |
1_060.txt |
AC |
24 ms |
19072 KB |
1_061.txt |
AC |
25 ms |
19072 KB |
1_062.txt |
AC |
25 ms |
19072 KB |
1_063.txt |
AC |
24 ms |
19072 KB |