BZOJ1488: [HNOI2009]图的同构 群论+Polya定理+组合数学

题解：

现在终于还算是明白了。

首先将边的存在性定义为两种颜色，这样就变成了一个Polya的经典问题。

但是如何考虑边的置换群呢？

我们首先考虑点的置换群。点的置换与边的置换是一一对应的。

点的置换显然有$O(n!)$种，但我们可以按照每个循环的大小进行分组，最终发现组数还是能够接受的。

考虑一个组的点置换，我们最终将方案数乘以这个组内有多少置换就行了。这一步可以用简单的组合数学知识来解决。

那么具体应该是怎样的呢？

对于一个循环而言，若循环大小为$n$，则会产生$n$种不同的置换。

对于若干个大小相同的循环事实上是等价的，也需要考虑这个影响。

具体看代码吧。

现在考虑如何将点置换转化为边置换，即将所有边划分为若干组可以轮换的边。

考虑那种两个端点在同一个点循环的边，则如果点循环的大小为$n$，我们可以分为差值分别为$1,2,...,\lfloor\frac{n}{2}\rfloor$的若干组。

考虑那种两个端点在不同的点循环的边，如果两个点循环的大小分别为$n,m$,脑补一下可以发现会出现$gcd(n,m)$组边。

接着套用Polya定理就行了。

这样的话，问题大概就得到了解决了。

代码：

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

int n,p;
int inv[20010];
int fac[61],g[61][61],pow2[10010];

inline int gcd(int a,int b){
	return(!b)?a:gcd(b,a%b);
}

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*=inv[stack[i]])%=p;
			(num*=inv[fac[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+=pow2[cir]*num)%=p;
		return;
	}
	for(int i=pre;i<=last;++i){
		stack[dep+1]=i;
		dfs(last-i,dep+1,i);
	}
}

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