Submission #3778578


Source Code Expand

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int mod=1e9+7;
const int maxn=100;
int n,m,k,ans=1,tot=1,tail,cnt,Time;
int pre[maxn*2+8],now[maxn+8],son[maxn*2+8],u[maxn+8],v[maxn+8];
int fac[maxn*2+8],fact[maxn*2+8],st[maxn+8];
int dfn[maxn+8],low[maxn+8],belong[maxn+8],num[maxn+8],siz[maxn+8];
int color[maxn+8];

int read()
{
    int x=0,f=1;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    return x*f;
}

void add(int u,int v)
{
    pre[++tot]=now[u];
    now[u]=tot;
    son[tot]=v;
}

void tarjan(int x,int fa)
{
    dfn[x]=low[x]=++Time;
    for (int p=now[x];p;p=pre[p])
	{
	    int child=son[p];
	    if (child==fa||dfn[child]>dfn[x]) continue;
	    st[++tail]=p>>1;
	    if (!dfn[child])
		{
		    tarjan(child,x);
		    low[x]=min(low[x],low[child]);
		}
	    else low[x]=min(low[x],dfn[child]);
	    if (low[child]>=dfn[x])
		{
		    ++cnt;
		    while(st[tail+1]!=(p>>1))
			{
			    int p=st[tail];
			    if (color[u[p]]!=cnt) color[u[p]]=cnt,siz[cnt]++;
			    if (color[v[p]]!=cnt) color[v[p]]=cnt,siz[cnt]++;
			    belong[p]=cnt,num[cnt]++;tail--;
			}
		}
	}
}

int C(int n,int m){return 1ll*fac[n]*fact[m]%mod*fact[n-m]%mod;}
int power(int a,int k)
{
    int sum=1;
    for (;k;k>>=1,a=1ll*a*a%mod)
	if (k&1)
	    sum=1ll*sum*a%mod;
    return sum;
}
int gcd(int n,int m){return n?gcd(m%n,n):m;}

int main()
{
    n=read(),m=read(),k=read();
    fac[0]=fact[0]=1;
    for (int i=1;i<=m+k;i++) fac[i]=1ll*fac[i-1]*i%mod;
    fact[m+k]=power(fac[m+k],mod-2);
    for (int i=m+k-1;i;i--) fact[i]=1ll*fact[i+1]*(i+1)%mod;
    for (int i=1;i<=m;i++)
	{
	    u[i]=read(),v[i]=read();
	    add(u[i],v[i]),add(v[i],u[i]);
	}
    for (int i=1;i<=n;i++)
	if (!dfn[i]) tarjan(i,0);
    for (int i=1;i<=cnt;i++)
	if (num[i]==1) ans=1ll*ans*k%mod;
	else
	    if (siz[i]==num[i])
		{
		    int tmp=0;
		    for (int j=1;j<=siz[i];j++) tmp=(tmp+power(k,gcd(j,siz[i])))%mod;
		    ans=1ll*ans*tmp*power(siz[i],mod-2)%mod;
		}
	    else ans=1ll*ans*C(num[i]+k-1,k-1)%mod;
    printf("%d\n",ans);
    return 0;
}
		
	    

Submission Info

Submission Time
Task F - Painting Graphs with AtCoDeer
User AlseoRoplyer
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2281 Byte
Status WA
Exec Time 1 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1300
Status
AC × 3
AC × 57
WA × 7
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 1 ms 256 KB
0_001.txt AC 1 ms 256 KB
0_002.txt AC 1 ms 256 KB
1_003.txt AC 1 ms 256 KB
1_004.txt AC 1 ms 256 KB
1_005.txt AC 1 ms 256 KB
1_006.txt AC 1 ms 256 KB
1_007.txt AC 1 ms 256 KB
1_008.txt AC 1 ms 256 KB
1_009.txt AC 1 ms 256 KB
1_010.txt AC 1 ms 256 KB
1_011.txt AC 1 ms 256 KB
1_012.txt AC 1 ms 256 KB
1_013.txt AC 1 ms 256 KB
1_014.txt WA 1 ms 256 KB
1_015.txt WA 1 ms 256 KB
1_016.txt AC 1 ms 256 KB
1_017.txt AC 1 ms 256 KB
1_018.txt WA 1 ms 256 KB
1_019.txt AC 1 ms 256 KB
1_020.txt AC 1 ms 256 KB
1_021.txt WA 1 ms 256 KB
1_022.txt WA 1 ms 256 KB
1_023.txt AC 1 ms 256 KB
1_024.txt AC 1 ms 256 KB
1_025.txt WA 1 ms 256 KB
1_026.txt AC 1 ms 256 KB
1_027.txt AC 1 ms 256 KB
1_028.txt AC 1 ms 256 KB
1_029.txt AC 1 ms 256 KB
1_030.txt AC 1 ms 256 KB
1_031.txt AC 1 ms 256 KB
1_032.txt AC 1 ms 256 KB
1_033.txt AC 1 ms 256 KB
1_034.txt AC 1 ms 256 KB
1_035.txt AC 1 ms 256 KB
1_036.txt AC 1 ms 256 KB
1_037.txt AC 1 ms 256 KB
1_038.txt AC 1 ms 256 KB
1_039.txt AC 1 ms 256 KB
1_040.txt AC 1 ms 256 KB
1_041.txt AC 1 ms 256 KB
1_042.txt AC 1 ms 256 KB
1_043.txt AC 1 ms 256 KB
1_044.txt AC 1 ms 256 KB
1_045.txt WA 1 ms 256 KB
1_046.txt AC 1 ms 256 KB
1_047.txt AC 1 ms 256 KB
1_048.txt AC 1 ms 256 KB
1_049.txt AC 1 ms 256 KB
1_050.txt AC 1 ms 256 KB
1_051.txt AC 1 ms 256 KB
1_052.txt AC 1 ms 256 KB
1_053.txt AC 1 ms 256 KB
1_054.txt AC 1 ms 256 KB
1_055.txt AC 1 ms 256 KB
1_056.txt AC 1 ms 256 KB
1_057.txt AC 1 ms 256 KB
1_058.txt AC 1 ms 256 KB
1_059.txt AC 1 ms 256 KB
1_060.txt AC 1 ms 256 KB
1_061.txt AC 1 ms 256 KB
1_062.txt AC 1 ms 256 KB
1_063.txt AC 1 ms 256 KB