Submission #1179778

---

Source Code Expand

#include<bits/stdc++.h>
#include<vector>
#define N 205
#define PAIR pair<int,int>
#define LL long long
using namespace std;
const int mo=1e9+7;
int head[N],len,nxt[N],num[N],ce,cd;
int n,m,k,f[N],C[N][N],pw[N],ans,dfn[N],low[N],clk,cut[N],st[N],top,vis[N],xyk;
int gcd(int x,int y){ return x ? gcd(y%x,x) : y;}
LL fpm(LL x,LL y){ LL s=1; while(y){ if(y&1) s=(s*x)%mo; y>>=1,x=(x*x)%mo;} return s;}
int cir(int n)
{
	int i,ans=0;
	for(i=1;i<=n;i++)
		ans=(ans+pw[gcd(i,n)])%mo;
	ans=(1LL*ans*fpm(n,mo-2))%mo;
	return ans;
}
void calc(int e)
{
	int x,y;
	if(top==1) ans=(1LL*ans*k)%mo,top=0;
	else{
		cd=ce=0,++xyk;
		while(top){
			x=num[st[top]^0];
			y=num[st[top]^1];
			ce++;
			if(vis[x]!=xyk) cd++,vis[x]=xyk;
			if(vis[y]!=xyk) cd++,vis[y]=xyk;
			if(st[top--]==e) break;
		  }
		if(cd==ce) ans=(1LL*ans*cir(cd))%mo;
		else ans=(1LL*ans*C[ce+k-1][k-1])%mo;
	  }
}
void tarjan(int t,int fa)
{
	int i;
	dfn[t]=low[t]=++clk,cut[t]=0;
	for(i=head[t];i;i=nxt[i]){
		if(num[i]==fa) continue;
		if(!dfn[num[i]]){
			st[++top]=i;
			tarjan(num[i],t),low[t]=min(low[t],low[num[i]]);
			if(low[num[i]]>=dfn[t]) cut[t]=1,calc(i);
		  }
		else{
			low[t]=min(low[t],dfn[num[i]]);
			if(dfn[num[i]]<dfn[t]) st[++top]=i;
		  }
	  }
}
int main()
{
	int i,j,x,y; ans=len=1;
	scanf("%d %d %d",&n,&m,&k);
	for(i=1;i<=m;i++){
		scanf("%d %d",&x,&y);
		num[++len]=y,nxt[len]=head[x],head[x]=len;
		num[++len]=x,nxt[len]=head[y],head[y]=len;
	  }
	C[0][0]=pw[0]=1;
	for(i=1;i<N;i++){
		C[i][0]=C[i][i]=1;
		for(j=1;j<i;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mo;
	  }
	for(i=1;i<N;i++) pw[i]=(1LL*pw[i-1]*k)%mo;
	for(i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i,0),top=0;
	cout<<ans;
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:58: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:60:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
                       ^

Judge Result