Submission #11898577

---

Source Code Expand

//Love and Freedom.
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define ll long long
#define inf 20021225
#define mdn 1000000007
#define N 100010
#include<stack>
using namespace std;
int read()
{
	int s=0,t=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')	t=-1; ch=getchar();}
	while(ch>='0' && ch<='9')	s=s*10+ch-'0',ch=getchar();
	return s*t;
}
int ksm(int bs,int mi)
{
	int ans=1;
	while(mi)
	{
		if(mi&1)	ans=1ll*ans*bs%mdn;
		bs=1ll*bs*bs%mdn; mi>>=1;
	}
	return ans;
}
struct edge{int to,lt;}e[N<<1];
int in[N],cnt,fac[N],inv[N];
void add(int x,int y)
{
	e[++cnt].to=y; e[cnt].lt=in[x]; in[x]=cnt;
	e[++cnt].to=x; e[cnt].lt=in[y]; in[y]=cnt;
}
int dfn[N],low[N],tms,col[N],cl,tot[N],edg[N]; ll mas[N];
stack<int> stk;
void tarjan(int x)
{
	dfn[x]=low[x]=++tms; stk.push(x);
	for(int i=in[x];i;i=e[i].lt)
	{
		int y=e[i].to;
		if(dfn[y])
			low[x]=min(low[x],dfn[y]);
		else
		{
			tarjan(y), low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x])
			{
				int w=0,p=0; ++cl;
				do
				{
					w=stk.top(); stk.pop(); mas[w]|=1ll<<cl; p++;
				}while(w!=y);
				tot[cl]=p+1; mas[x]|=1ll<<cl;
			}
		}
	}
}
int C(int n,int m){return n<m?0:1ll*fac[n]*inv[m]%mdn*inv[n-m]%mdn;}
int ans=1,u[N],v[N],n,m,k;
void solve()
{
	fac[0]=1;
	for(int i=1;i<=m+k;i++)	fac[i]=1ll*fac[i-1]*i%mdn;
	inv[m+k]=ksm(fac[m+k],mdn-2);
	for(int i=m+k;i;i--)	inv[i-1]=1ll*inv[i]*i%mdn;
	for(int i=1;i<=n;i++)	if(!dfn[i])	tarjan(i);
	for(int i=1;i<=m;i++)
	{
		if(!(mas[u[i]]&mas[v[i]]))	ans=1ll*ans*k%mdn;
		else
		{
			ll ms=mas[u[i]]&mas[v[i]];
			for(int j=1;j<=cl;j++)	if(ms>>j&1)
				edg[j]++;
		}
	}
	for(int i=1;i<=cl;i++)	if(edg[i]>=tot[i])
	{
		if(edg[i]==tot[i])
		{
			int val=0;
			for(int j=1;j<=edg[i];j++)
			{
				val+=ksm(k,__gcd(j,edg[i]));
				if(val>=mdn)	val-=mdn;
			}
			ans=1ll*ans*ksm(edg[i],mdn-2)%mdn*val%mdn;
		}
		else	ans=1ll*ans*C(edg[i]+k-1,k-1)%mdn;
	}
	else	ans=1ll*ans*k%mdn;
	printf("%d\n",ans);
}
int main()
{
	n=read(),m=read(),k=read();
	for(int i=1;i<=m;i++)	add(u[i]=read(),v[i]=read());
	solve();
	return 0;
}

Submission Info

Judge Result