【學習筆記】群論

群\((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
           

說明/提示

題解

#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;
}