「bzoj1478」「SGU282」Isomorphism - Polya计数+数论

题目大意

    给定一个$N$个结点的无向完全图（任意两个结点之间有一条边）， 现在你可以用$M$种颜色对这个图的每条边进行染色，每条边必须染一种颜色。若两个已染色的图，其中一个图可以通过结点重新编号而与另一个图完全相同， 就称这两个染色方案相同。现在问你有多少种本质不同的染色方法，输出结果$\bmod P$。$P$是一个大于$N$的质数。

---

题目分析

这道题显然要用Polya计数解决等价类问题。

不妨参考隔壁CQzhangyu大爷的题解，写的很详细我就懒得说了。

不过其例子少打了换行（我才不会告诉你我盯着它看了半个小时这是什么玩意儿）：

$$\begin{pmatrix}1&2&3 \\ 2&1&3\end{pmatrix}\rightarrow\begin{pmatrix}(1,2)&(1,3)&(2,3) \\ (1,2)&(2,3)&(1,3)\end{pmatrix}$$ $$\begin{pmatrix}1&2&3 \\ 1&3&2\end{pmatrix}\rightarrow\begin{pmatrix}(1,2)&(1,3)&(2,3) \\ (1,3)&(1,2)&(2,3)\end{pmatrix}$$

关于其题解中循环的长度，画画图即可知道了。
另外，因为是循环，循环可以轮换一下意义相同，所以需要乘$(L_1-1)!(L_2-1)!…(L_K-1)!$而不是$L_1!L_2!…L_K!$。

---

代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

inline int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
	while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
	return num*bj;
}

const int maxn=55;

int n,a[maxn],G[maxn][maxn];
LL m,p,Pow[maxn*maxn+maxn],fac[maxn],inv[maxn],invf[maxn],ans=0;

int gcd(int a,int b) {return b==0?a:(G[a][b]?G[a][b]:G[a][b]=gcd(b,a%b));}

void Dfs(int dep,int sum,int last) {
	if(!sum) {
		LL s=fac[n],c=0,len=0;
		for(int i=1; i<=dep; i++) {
			len++;
			if(i==dep||a[i]!=a[i+1])s=s*invf[len]%p,len=0;
			s=s*inv[a[i]]%p;
			c+=a[i]>>1;
			for(int j=1; j<i; j++)c+=gcd(a[i],a[j]);
		}
		ans=(ans+Pow[c]*s)%p;
		return;
	}
	for(int i=min(sum,last); i>=1; i--)a[dep+1]=i,Dfs(dep+1,sum-i,i);
}

int main() {
	n=Get_Int();
	m=Get_Int();
	p=Get_Int();
	Pow[0]=1;
	for(int i=1; i<=n*n+n; i++)Pow[i]=Pow[i-1]*m%p;
	fac[1]=inv[1]=invf[1]=fac[0]=inv[0]=invf[0]=1;
	for(int i=2; i<=n; i++) {
		fac[i]=fac[i-1]*i%p;
		inv[i]=p-(p/i)*inv[p%i]%p;
		invf[i]=invf[i-1]*inv[i]%p;
	}
	Dfs(0,n,n);
	printf("%lld\n",ans*invf[n]%p);
	return 0;
}