自动搬运

查看原文

来自洛谷，原作者为

	寻逍遥2006 晓看天色暮看云，行也思君，坐也思君；春赏百花冬赏雪，醒也思卿，梦也思卿

搬运于2025-08-24 22:40:54，当前版本为作者最后更新于2023-04-20 13:05:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意：就对于一个有 $n$ 个节点的图进行 $k$ 染色，本质不同的染色方式有多少种。

其中，两种染色方式相同称为对其中一个图的所有点重编号之后，两个图同构且对应点颜色相同。

考虑使用 Polya 定理，那么我们就需要找到所有置换，满足对点进行置换之后图仍然同构。

比如说，对于样例来说，所有满足条件的置换为 $(1,2,3)$ 和 $(3,2,1)$。

由于 $n\leqslant 10$，所以可以考虑暴力枚举每一种置换是否满足上述条件既可。单次判断可以直接使用 $O(m)$ 或者 $O(n^2)$ 的暴力判断。

找到置换群 $G$ 之后，根据 Polya 定理，答案即为 $\dfrac{1}{|G|}\sum\limits_{g\in G}m^{\sigma(g)}$，其中 $\sigma(g)$ 表示每一个置换 $g$ 的环的个数，这个部分可以 $O(n)$ 求出。

总体复杂度为 $O(m\times n!+|G|\times n)$ 或者 $O(n^2\times n!+|G|\times n)$。

由于时限宽松，这里给出一个较劣的 $O(n^2\times n!+|G|\times n)$ 算法。

#include <bits/stdc++.h>
#define Mod 10007
using namespace std;
int Qread()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	return x;
}
long long qpow(long long a,long long p)
{
	long long ret=1;
	for(;p;p>>=1,a=a*a%Mod)
		if(p&1) ret=ret*a%Mod;
	return ret;
}
int n,m,k,u,v;
long long ans,cnt;
bool ed[20][20];
int p[20];bool vis[20];
bool chk()
{
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
		if(ed[i][j]^ed[p[i]][p[j]])
			return false;
	return true;
}
int get_cir()
{
	int ret=0,nw;
	for(int i=1;i<=n;i++) vis[i]=false;
	for(int i=1;i<=n;i++)
	{
		if(vis[i]) continue;
		nw=i;
		do vis[nw]=true,nw=p[nw];
		while(nw!=i);
		ret++;
	}
	return ret;
}
int main()
{
	n=Qread(),m=Qread(),k=Qread();
	for(int i=1;i<=n;i++)
		p[i]=i;
	for(int i=1;i<=m;i++)
	{
		u=Qread(),v=Qread();
		ed[u][v]=ed[v][u]=true;
	}
	do
	{
		if(!chk()) continue;
		cnt++;
		ans=(ans+qpow(k,get_cir()))%Mod;
	}while(next_permutation(p+1,p+n+1));
	printf("%d\n",ans*qpow(cnt,Mod-2)%Mod);
	return 0;
}