BZOJ1815: [Shoi2006]color 有色图 群论+Polya定理+组合数学

题解：

具体请参考http://wyfcyx.is-programmer.com/posts/181716.html

对于这道题目则要注意一点复杂度的问题，否则会T。

代码：

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
int n,m,p;
int fac[61],ifac[61],_inv[61],g[61][61],powm[10010];

inline int gcd(int a,int b){
	return(!b)?a:gcd(b,a%b);
}
inline int pow(int x,int y,int p){
	int re=1,t=x;
	for(;y;y>>=1,t=(ll)t*t%p)
		if(y&1)
			re=(ll)re*t%p;
	return re;
}
inline int inv(int x){
	return pow(x,p-2,p);
}

int stack[61],ans;
inline void dfs(int last,int dep,int pre){
	if(last==0){
		int i,j,k,num=fac[n];
		for(i=1;i<=dep;i=j+1){
			for(j=i;j!=dep&&stack[j]==stack[j+1];++j);
			for(k=i;k<=j;++k)
				num=(ll)num*_inv[stack[i]]%p;
			num=(ll)num*ifac[j-i+1]%p;
		}
		int cir=0;
		for(i=1;i<=dep;++i)
			cir+=stack[i]>>1;
		for(i=1;i<=dep;++i)
			for(j=i+1;j<=dep;++j)
				cir+=g[stack[i]][stack[j]];
		ans=((ll)ans+(ll)num*powm[cir])%p;
		return;
	}
	for(int i=pre;i<=last;++i){
		stack[dep+1]=i;
		dfs(last-i,dep+1,i);
	}
}

int main(){
	cin>>n>>m>>p;
	int i,j;
	for(fac[0]=1,i=1;i<=n;++i)
		fac[i]=(ll)fac[i-1]*i%p;
	for(i=0;i<=n;++i)
		ifac[i]=inv(fac[i]);
	for(_inv[1]=1,i=2;i<=n;++i)
		_inv[i]=p-(ll)(p/i)*_inv[p%i]%p;
	for(i=1;i<=n;++i)
		for(j=1;j<=n;++j)
			g[i][j]=gcd(i,j);
	for(powm[0]=1,i=1;i<=10000;++i)
		powm[i]=(ll)powm[i-1]*m%p;
	
	dfs(n,0,1);
	
	cout<<(ll)ans*ifac[n]%p<<endl;
	
	return 0;
}