Submission #1691998

---

Source Code Expand

#include<bits/stdc++.h>
#define mo 1000000007
using namespace std;
int n,m,kk,pointnum,edgenum,tim,num,top;
int dfn[100010],low[100010],po[100010],p[100010],q[100010];
int vis[100010];
vector <int> des[100010];
set<int> mp[100010];
pair<int,int> st[100010];
void tarjan(int s,int pre=0)
{
	dfn[s]=low[s]=++tim;
	for (int k=0;k<des[s].size();k++) if (des[s][k]!=pre)
	{
		if (!dfn[des[s][k]])
		{
			st[++top]=make_pair(s,des[s][k]);
			tarjan(des[s][k],s);
			if (low[des[s][k]]>=dfn[s])
			{
				num++;
				while (st[top]!=make_pair(s,des[s][k]))
				{
					mp[st[top].first].insert(num);mp[st[top].second].insert(num);
					top--;
				}
				mp[st[top].first].insert(num);mp[st[top].second].insert(num);top--;
			}
			low[s]=min(low[s],low[des[s][k]]);
		}
		else low[s]=min(low[s],dfn[des[s][k]]);
	}
	//cerr<<s<<' '<<pre<<' '<<dfn[s]<<' '<<low[s]<<endl;
}
long long getmi(int a,int x)
{
	long long ans=1;
	while (x)
	{
		if (x&1) ans=ans*a%mo;
		a=(long long)a*a%mo;
		x>>=1;
	}
	return ans;
}
long long fac[100010],nifac[100010];
long long C(int n,int m){return fac[n]*nifac[m]%mo*nifac[n-m]%mo;}
long long polya(int n)
{
	long long ans=0;
	for (int i=1;i<=n;i++) ans=(ans+getmi(kk,__gcd(i,n)))%mo;
	return ans*getmi(n,mo-2)%mo;
}
int pp[100010],qq[100010];
int main()
{
	scanf("%d%d%d",&n,&m,&kk);
	fac[0]=nifac[0]=1;
	for (int i=1;i<=n+kk;i++){fac[i]=fac[i-1]*i%mo;nifac[i]=getmi(fac[i],mo-2);}
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d",&p[i],&q[i]);
		des[p[i]].push_back(q[i]);des[q[i]].push_back(p[i]);
	}
	
	for (int i=1;i<=n;i++) if (!dfn[i]) tarjan(i);
	
	for (int i=1;i<=n;i++)
	for (set<int>::iterator it=mp[i].begin();it!=mp[i].end();it++) pp[*it]++;
	
	for (int s=1;s<=n;s++)
	for (int k=0;k<des[s].size();k++)
	{
		int t=des[s][k];
		for (set<int>::iterator it=mp[s].begin();it!=mp[s].end();it++) if (mp[t].count(*it)) {qq[*it]++;break;}
	}
	
	long long ans=1;
	for (int i=1;i<=num;i++)
	{
		qq[i]/=2;
		if (pp[i]>qq[i]) ans=ans*kk%mo;
		else if (pp[i]==qq[i]) ans=ans*polya(pp[i])%mo;
		else ans=ans*C(qq[i]+kk-1,kk-1)%mo;
	}
	cout<<ans<<endl;
}
	
		

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:57:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&m,&kk);
                           ^
./Main.cpp:62:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&p[i],&q[i]);
                            ^

Judge Result