BZOJ4245: [ONTAK2015]OR-XOR 贪心
BZOJ1815: [Shoi2006]color 有色图 群论+Polya定理+组合数学

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

shinbokuow posted @ Sep 04, 2015 08:18:35 PM in BZOJ with tags 数学 群论 Polya定理 , 1961 阅读

 

题解:

现在终于还算是明白了。

首先将边的存在性定义为两种颜色,这样就变成了一个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;
}
Alyssa 说:
Feb 01, 2023 08:07:35 PM

After much confusion, I am delighted to have finally understood the concept of edge permutations. It is a Polya classic problem which defines the existence of edges in two colours. The complexity of the problem further increases when one considers permutations of edges. We <a href="https://eatcbdgummies.com">Best CBD Products</a> first consider permutations of points and realise that there is a one-to-one correspondence between point replacement and edge replacement. There are O(n!) permutations of points which can be grouped according to the size of each cycle, thus making the number of permutations still manageable.

Emma 说:
Feb 01, 2023 08:08:27 PM

After much confusion, I am delighted to have finally understood the concept of edge permutations. It is a Polya classic problem which defines the existence of edges in two colours. The complexity of the problem further increases when one considers permutations of Best CBD Products edges. We first consider permutations of points and realise that there is a one-to-one correspondence between point replacement and edge replacement. There are O(n!) permutations of points which can be grouped according to the size of each cycle, thus making the number of permutations still manageable.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter