【学习笔记】群论

群\((group)\)

一、定义:由集合\(G\)与二元运算\(\times\)构成的,满足以下三个性质的代数结构

  1. 结合律 \(:\forall a,b,c \in G,(a\times b)\times c=a\times(b\times c)\)
  1. 存在幺元\((\)单位元\()\) \(:\exists e\in G,\)满足$ \forall a\in G,a\times e=e\times a=a,$且幺元唯一
  1. 存在逆元 \(:\forall a\in G,\exists a^{-1}\in G,\)满足\(a\times a^{-1}=a^{-1}\times a=e,\)且\(\forall a\in G,a^{-1}\)唯一

一个群可记为\((G,\times,e)\)或\((G,\times)\)

集合\(G\)的基数记为群\((G,\times)\)的阶,当阶为某一确定整数是,则群\((G,\times)\)为有限群,否则为无限群

二、置换

\(G\)上的置换是一个\(n\)元的变换 \(\sigma G\rightarrow G,i\rightarrow \sigma(i)\)可以写成\(:\)

\[\begin{bmatrix}1&2&…&n\\\sigma(1)&\sigma(2)&…&\sigma(n)\end{bmatrix} \]

置换是一种双射

将置换的上下两行交换后可得到原置换的逆元

置换的乘法:

设\(\sigma1,\sigma2\)是\(G\)上的两个置换,则定义乘法\(\sigma=\sigma1\times\sigma2\)为\(:i\rightarrow\sigma1(\sigma2(i))\)

例\(:\)

\[\begin{bmatrix}1&2&3 \\2&3&1\end{bmatrix}\times\begin{bmatrix}1&2&3 \\3&2&1\end{bmatrix}=\begin{bmatrix}1&2&3 \\1&3&2\end{bmatrix} \]

置换的乘法规则为从右往左运算

轮换: 轮换是特殊的置换,记为\((a_1,a_2,…,a_n)\),其对应的置换满足\(\sigma(a_i)=a_i+1,\sigma(a_n)=a_1,\)任取其他未被涉及到的元素\(b,\)满足\(\sigma(b)=b\)

定理: 任何一个置换都可以写成若干个不相交的轮换的乘积

例\(:\)

\[\begin{bmatrix}1&2&3&4&5\\2&4&5&1&3\end{bmatrix}=(3\ 5)\times(1\ 2\ 4) \]

可以证明置换的轮换表示法是唯一的

置换群: 由一些置换和置换的乘法构成的群

二元关系: 满足自反性、对称性、传递性的二元关系

一个基于\(n\)元集合的置换群可以定义一个\(a_1,...,a_n\)这样一个数组之间的等价关系,所有具有等价关系的称为一个等价类,一般
题目中要求的”本质不同的方案数” 实际上就是求等价类的数目,
也就是说,在这里,我们认为置换作用在一个数组的下标上

不动点: 一个数组如果在置换的作用下不变,我们称它为这个置
换的一个不动点

三、相关定理

\(Burnside\)引理: 对于一个置换群 G,其在集合 C 中的等价类数
目为:所有置换的不动点个数的平均值

\(Pólya\)定理: 设\(\overline{G}=\begin{Bmatrix}\overline{P_1},\overline{P_2},…,\overline{P_n}\end{Bmatrix}\)是\(n\)个对象的一个置换群,\(C(P_k)\)是置换Pk的循环的个数,用\(m\)种颜色对\(n\)个对象着色, 着色方案数为:

\[\large{L=\frac{1}{|G|}\sum_{p\in G}m^{C(p)}} \]

用较易懂的语言说就是:对于一个置换\(i\rightarrow\sigma(i)\),其不动点个数为\(2^k\),其中\(k\)代表这个置换能表示成\(k\)个不相交轮换乘积的形式

四、题目选讲

例题:Luogu P1446 [HNOI2008]Cards

题目描述

小春现在很清闲,面对书桌上的\(n\)张牌,他决定给每张牌染色,目前小春拥有\(3\)种颜色:红色,蓝色,绿色。他询问\(Son\)有多少种染色方案,\(Sun\)很快就给出了答案。

进一步,小春要求染出\(S_r\) 张红色,\(S_b\)张蓝色,\(S_g\)张绿色。他又询问有多少种方案,\(Son\)想了一下,又给出了正确答案。最后小春发明了\(m\)种不同的洗牌法,这里他又问\(Son\)有多少种不同的染色方案。两种染色方法相同当且仅当其中一种可以通过任意的洗牌法\((\)即可以使用多种洗牌法,而每种方法可以使用多次\()\)洗成另一种。

\(Son\)发现这个问题有点难度,决定交给你,由于答案可能很大,你只需要求出答案对于\(P\)取模的结果。保证\(P\)为一个质数。

输入格式

第一行输入\(5\)个整数,依次表示:\(S_r,S_b,S_g,m,P\) $(m\le 60,m+1\leq p\leq 100) \(。其中,题面所提及的\)n\(为\) S_r+S_b+S_g \(,即\) n=S_r+S_b+S_g $。

接下来\(m\)行,每行描述一种洗牌法,每行有\(n\)个用空格隔开的整数 \(X_1X_2...X_n\),保证其为\(1\)到\(n\)的一个排列,表示使用这种洗牌法,第\(i\)位变为原来的\(X_i\)位的牌。输入数据保证任意多次洗牌都可用这\(m\)种洗牌法中的一种代替,且对每种洗牌法,都存在一种洗牌法使得能回到原状态。

同时,对于$ 100% \(的数据满足\) \max{S_r,S_b,S_g}\le 20 $

输出格式

不同的染色方法对\(P\)取模的结果。

输入输出样例

输入 #1

1 1 1 2 7
2 3 1
3 1 2

输出 #1

2

说明/提示

有\(2\)种本质上不同的染色法:\(RGB\)和\(RBG\),使用洗牌法\(231\)一次,可得\(GBR\)和\(BGR\),使用洗牌法\(312\)一次,可得\(BRG\)和\(GRB\)。

题解

可以发现题目给定的\(m\)种洗牌法并没有构成一个置换群,但这个群没有幺元,因此可以加上一个\(i\rightarrow i\)的置换,然后用\(Burnside\)引理计算答案。注意因为有颜色的限制,不能用\(Pólya\)定理,可以用一个类似背包的\(dp\)数组,对于每种洗牌法,先处理出每个位置的最小循环长度,然后以颜色个数为背包容量dp,最后直接除以\((m+1)\)

代码:

#include<bits/stdc++.h>
#define rg register
#define il inline
#define int long long
#define inf 0x3f3f3f3f
#define N 110
#define ls k<<1
#define rs k<<1|1
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
il int read(){
	int w=0,h=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')h=-h;ch=getchar();}
	while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
	return w*h;
}
void write(int x){
	if(x<0)x=-x,putchar('-');
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
int r,b,g,n,m,mod,tot,ans;
int rep[N],sz[N],dp[N][N][N];
bool vis[N];
int ksm(int b,int k){
	int s=1;
	while(k){
		if(k&1)s=s*b%mod;
		b=b*b%mod;
		k>>=1;
	}
	return s%mod;
}
int inv(int a){return ksm(a,mod-2);}
int calc(){
	memset(vis,0,sizeof(vis));
	memset(dp,0,sizeof(dp));
	tot=0;
	for(int i=1;i<=n;i++)
		if(!vis[i]){
			int p=i,len=0;
			while(!vis[p])vis[p]=1,p=rep[p],len++;
			sz[++tot]=len;
		}
	dp[0][0][0]=1;
	for(int l=1;l<=tot;l++)
		for(int i=r;i>=0;i--)
			for(int j=b;j>=0;j--)
				for(int k=g;k>=0;k--){
					if(i>=sz[l])dp[i][j][k]=(dp[i][j][k]+dp[i-sz[l]][j][k])%mod;
					if(j>=sz[l])dp[i][j][k]=(dp[i][j][k]+dp[i][j-sz[l]][k])%mod;
					if(k>=sz[l])dp[i][j][k]=(dp[i][j][k]+dp[i][j][k-sz[l]])%mod;
				}
	return dp[r][b][g]%mod;
}
signed main(){
	r=read();b=read();g=read();
	n=r+b+g;
	m=read();mod=read();
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++)rep[j]=read();
		ans=(ans+calc())%mod;
	}
	for(int i=1;i<=n;i++)rep[i]=i;
	ans=(ans+calc())%mod;
	printf("%lld\n",ans*inv(m+1)%mod);
	return 0;
}
上一篇:JS练习(4)


下一篇:康托展开