polya定理&&burnside引理

专题地址:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=36645#overview
这里有更完整的:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=484
看了下大白书,做下上面的习题。两个定理叙述很简单,证明暂时没看,先把题做的差不多再说。。
一些小结:
1.置换。一对一的函数
2.置换的乘法:满足结合律,但不满足交换律
3.置换分解成几个循环的乘积,因为假如将一个置换看成一条有向边那么形成的图中每个点都是入度为1,出度为1.所以一定是若干个圈。
4.独立的循环之间的乘法满足交换律
5.设A是与元素个数为n的循环,则:
(1)若n为奇数,则A*A是一个n个元素的循环
(2)若n为偶数,则A*A是两个n/2个元素且相互独立的循环的乘积
6.引出:由5的性质可知:
(1)一个长度n为奇数的循环B,一定可以找到一个长度为n的循环A,满足A^2=B;
(2)两个长度都为n的不相交循环B和C,一定可以找到长度为2*n的循环A,使得A^2=B*C;
7.继续引出:
(1)长度n为奇数的循环既可以是两个长度为n的循环乘出来的,也可以是两个长度为2n的循环乘出来的。
(2)长度n为偶数的循环只可能是两个长度为2n的循环乘出来的。
下面是一些题目
UVA 10294 Arif in Dhaka (First Love Part 2)
数学推算。。

#include<stdio.h>
#include<math.h>
typedef long long ll;
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
ll fact[15][60];
int main()
{
	int i,j;
	int n,t;
	for(i=1;i<=10;i++)
		fact[i][1]=(ll)i;
	for(i=1;i<=10;i++)
		for(j=2;j<=50;j++)
			fact[i][j]=fact[i][j-1]*(ll)i;
	while(~scanf("%d%d",&n,&t))
	{
		ll a=0,b=0;
		for(i=0;i<=n-1;i++)
			a+=fact[t][gcd(n,i)];
		b=n*(fact[t][(n+1)/2]+fact[t][(n+2)/2])/2;
		printf("%lld ",a/n);
		printf("%lld\n",(a+b)/(2*n));
	}
	return 0;
}

UVALive 3641 Leonardo’s Notebook
上述的几点“引出”。。

#include<stdio.h>
#include<string.h>
char s[30];
int ring[30];
bool visit[30];
int dfs(int cur)
{
	int ret=1;
	if(visit[cur]) return 0;
	visit[cur]=1;
	ret+=dfs(s[cur]-'A'+1);
	return ret;
}
int main()
{
	int i,j;
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%s",s+1);
		memset(ring,0,sizeof(ring));
		memset(visit,0,sizeof(visit));
		for(i=1;i<=26;i++)
		{
			if(visit[i]) continue;
			int ret=dfs(i);
			ring[ret]++;
		}
		for(i=1;i<=26;i++)
			if(!(i&1) && ring[i]&1) break;
		if(i<=26) printf("No\n");
		else printf("Yes\n");
	
	}
	return 0;
}

UVA 11077 Find the Permutations
递推,具体见lrj的训练指南。

#include<stdio.h>
#include<string.h>
typedef unsigned long long ll;
ll f[22][22];
int main()
{
	int i,j;
	int n,k;
	memset(f[1],0,sizeof(f[1]));
	f[1][0]=1;
	for(i=2;i<=21;i++)
		for(j=0;j<i;j++)
		{
			if(j==0) f[i][j]=1;
			f[i][j]=f[i-1][j]+f[i-1][j-1]*(i-1);
		}
	while(~scanf("%d%d",&n,&k) && !(n==0 && k==0))
		printf("%llu\n",f[n][k]);
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>