群
一些基础
子群
若(H)是(G)的子集且(<H,op>)为群,则(<H,op>)为(<G,op>)的子群
则(H)既满足封闭性且求逆封闭,(forall a,bin H,abin H,a^{-1}in H)
等价于(forall a,bin H,ab^{-1}in H)
一些特殊特殊的子群:
生成子群:(ain G),则(<{a^i,iin Z},op>)称为生成子群
正规化子:(ain G),则(<{x|ax=xa,xin G>)称为正规化子,记为(N(a))
共轭子群:(ain G,H)为(G)的子群,则(xHx^{-1})称为(H)的共轭子群
等价类
等价关系:满足自反性(a=a),对称性(a=bLeftrightarrow b=a),传递性(a=b,b=cLeftrightarrow a=c)((=)代表的是等价关系)
等价类:(x)的等价类([x]_R={y|<x,y>in R}),(R)是满足某种等价关系两个元素所有集合
可以认为是把等价关系看作边,([x]_R)是(x)所在联通块的大小
商集:([A/R])指在以(R)为等价关系时等价类的集合
陪集
陪集分为右陪集与左陪集,两个没区别
对于(ain G),(H)是(G)的子群,称(Ha={ha|hin H})为(H)的右陪集
如果(H)为有限集,则(|Ha|=|H|)(不会证)
Lagrange定理
设(H)为(G)的子群,则(|G|)为(|H|)的倍数
考虑用陪集分解群
首先有个结论,(forall a,bin G,H)为(G)的子群,(ain HbLeftrightarrow Ha=HbLeftrightarrow ab^{-1}in H)
若已知(ain Hb),则(a=h_1b,h_1in H),(forall h_2in H),(h_2a=h_2h_1b),且(h_2h_1in H)
则(Hasubseteq Hb),反过来同理的(Hbsubseteq Ha),即(Ha=Hb)
若已知(Ha=Hb),则(exist h_1,h_2in H,h_1a=h_2b),(ab^{-1}=h_1^{-1}h_2in H)
若已知(ab^{-1}in H),则(ab^{-1}=hin H),则(a=hbin Hb)
如果将(Ha=Hb)视为一种等价关系,(H)一定单独是一个等价类
若(anotin H),则(Hanot=He),即(a)一定不与(e)在同一等价类
又(|Ha|=|H|),所以所有等价类大小相同
即(dfrac{|G|}{|H|}=|[G/R]|,R={<a,b>,Ha=Hb})
由此还可以得到共轭类分解
共轭关系也是一种等价关系,将(ain G),所有与(a)共轭的(b)形成的集合称为共轭类
(a)所在的共轭类大小为(dfrac{|G|}{|N(a)|})
令(x,yin G,xax^{-1}=yay^{-1})
(xa=yay^{-1}xRightarrow y^{-1}xa=ay^{-1}xRightarrow y^{-1}xin N(a)Rightarrow xN(a)=yN(a))
如果沿用陪集分解的思路,因为(xN(a)=yN(a))则(x,y)属于同一个等价类
用(N(a))陪集分解,对于其中的一个等价类中所有的元素(x),(xax^{-1})确定(a)的一个共轭
则共轭类的大小即为(N(a))陪集分解后的等价类个数
置换群相关定理
置换群
置换群即为一个(n)元排列(P)组成的集合,定义运算(PG=(G_{P_i}))
可证满足封闭性与求逆封闭
如果将(i)和(P_i)连有向边,则图为若干个不相交的环((n)条边(n)个点)
当然,有时置换群不一定是一个排列的集合,但一定是置换的集合
轨道-稳定子群定理
定义一个集合(A),(G)为一个作用于(A)的置换群,(ain A)
定义(G^a={g|g(a)=a,gin G }),称为稳定子群
(G(a)={g(a),gin G }),称为轨道
(|G|=|G(a)|times|G^a|),证明如下
设(x,yin G),且(x(a)=y(a)),则(Leftrightarrow a=x^{-1}(y(a))Leftrightarrow x^{-1}yin G^aLeftrightarrow xG^a=yG^a)
将(G)以(G^a)陪集分解,则当(x(a)=y(a))时(x,y)属于同一等价类
考虑等价类的个数即为有多少个不同的(x(a))即为(|G(a)|)
Burnside 引理
([A/G]=dfrac{1}{|G|}sumlimits_{gin G}[A^g]),(A^g)的定义与(G^a)类似,就是(A^g={a|g(a)=a,ain A })
(|G^a|=dfrac{|G|}{|G(a)|})，两边同时求和
(sumlimits_{ain A}|G^a|=sumlimits_{ain A}dfrac{|G|}{|G(a)|}=|G|sumlimits_{ain A}dfrac{1}{|G(a)|})
观察(sumlimits_{ain A}dfrac{1}{|G(a)|})，本质为轨道个数(每一个(a)所在的等价类大小分之(1)求和就是等价类的个数)=([A/G])
(sumlimits_{ain A}|G^a|=sumlimits_{gin G}[A^g]=|G|times|[A/G]|)
即([A/G]=dfrac{1}{|G|}sumlimits_{gin G}[A^g])
在这里我们给问题赋予一个实际意义
考虑(A)表示问题的所有方案,(G)为问题视为重复方案的置换
([A/G])即为将(G)看作一个等价关系的集合后划分出的等价类集合
(G^a)即为满足对(a)置换作用后依旧不变的置换,(A^g)差不多
(G(a))为与(a)一起视为一种方案的方案集合,也可一看作是(a)所在的等价类
再具体一点的例子就是环的着色问题
Pólya 定理
具体到染色问题,假设有(m)种颜色
则(A^g=m^{c(g)}),(c(g))为(g)的不相交循环个数
【模板】Pólya 定理
给定一个 (n) 个点，(n) 条边的环，有 (n) 种颜色，给每个顶点染色，问有多少种本质不同的染色方案，答案对 (10^9+7) 取模
注意本题的本质不同，定义为：只需要不能通过旋转与别的染色方案相同。
很明显(G)为一个轮换了(i)次的置换群
问题在于计算(c(g)),考虑(g)是轮换了(i)次的的置换,当前位置为(p)
(p->(p+i)mod n->(p+2i)mod n.....p'mod n=p)
即(p+(n/c(g))i=p+kn),即(c(g)=dfrac{i}{k})，则(c(g))既为(n)的因数也为(i)的因数且最大
则(c(g)=gcd(i,n))
([A/G]=dfrac{1}{|G|}sumlimits_{gin G} n^{c(g)}=dfrac{1}{n}sumlimits_{i=1}^nn^{gcd(i,n)})
令(f(x)=n^x)
([A/G]=dfrac{1}{n}sumlimits_{i=1}^nf(gcd(i,n))=dfrac{1}{n}sumlimits_{d|n}f(d)sumlimits_{i=1}[gcd(i,n)=d]=dfrac{1}{n}sumlimits_{d|n}f(d)phi(dfrac{n}{d}))
这里用(dfs)凑因子可以做到(Theta(sqrt n))
#include<bits/stdc++.h> using namespace std; const int MOD=1e9+7; int t; int n; int Pow(int a,int b,int p) { int res=1; int base=a; while(b) { if(b&1) { res=((long long)res*base)%p; } base=((long long)base*base)%p; b>>=1; } return res; } vector<pair<int,int> >Rec; int Phi[105][105]; int Pri[105][105]; int Used[105]; int Res=0; void dfs(int x) { if(x==Rec.size()) { int d=1; int phi=1; for(int i=0;i<Rec.size();i++) { d=(d*Pri[i][Used[i]]); phi=(phi*Phi[i][Used[i]]); } Res=((long long)Res+((long long)phi*Pow(n,(n/d)-1,MOD))%MOD)%MOD; return; } int Lim=Rec[x].second; for(int i=0;i<=Lim;i++) { Used[x]=i; dfs(x+1); } } int main() { scanf("%d",&t); while(t--) { Rec.clear(); scanf("%d",&n); Res=0; int now=n; for(int d=2;d*d<=now;d++) { if(now%d==0) { int Tot=0; while(now%d==0) { now/=d; Tot++; } Rec.push_back(make_pair(d,Tot)); } } if(now>1) { Rec.push_back(make_pair(now,1)); } for(int i=0;i<Rec.size();i++) { int Lim=Rec[i].second; int p=Rec[i].first; Phi[i][0]=1; Pri[i][0]=1; for(int j=1;j<=Lim;j++) { Pri[i][j]=Pri[i][j-1]*p; Phi[i][j]=Pri[i][j]-Pri[i][j-1]; } } dfs(0); printf("%dn",Res); } } Magic Bracelet
金妮的生日快到了。哈利波特正在为他的新女友准备生日礼物。礼物是一个由(n)颗魔法珠组成的魔法手镯。有(m)种不同的魔珠。每种珠子都有其独特的特征。将许多珠子串在一起，将制作一个漂亮的圆形魔法手镯。正如哈利波特的朋友赫敏所指出的那样，某些种类的珠子会相互作用并爆炸，哈利波特必须非常小心地确保这些对的珠子不会并排串在一起,有无数种珠子。如果忽略围绕手镯中心旋转产生的重复，哈利能制作多少种不同的手镯？找到取模 (9973) 的答案。
同样定义(G)为轮换(i)次的置换群,但由于不能随便染色,所以不能用(Pólya)定理
([A/G]=dfrac{1}{|G|}sumlimits_{gin G}|A^g|)
瓶颈在于计算(|A^g|)
我们将(g)拆分成不同的循环,这些循环的内部的点颜色是相同的且每个循环大小相同,问题是不同循环之间的关系
如果我们把一个循环看成一个点,再将和他有关系的连边,最后连出还是一个环
我们可以考虑只在这个环上计算答案
设(f(x))为长度为(x)的环时的答案
([A/G]=dfrac{1}{n}sumlimits_{gin G}|A^g|=dfrac{1}{n}sumlimits_{d|n}f(d)phi(dfrac{n}{d}))
现在问题在与如何计算(f(x))
构造一个邻接矩阵(T),矛盾为(0)，否则为(1),则(T^x)时的对角线之和即为(f(x))
#include<cstdio> #include<vector> #include<utility> #include<cstring> using namespace std; const int MOD=9973; int t; int m; int x,y; int k; int Pow(int a,int b,int p) { int res=1; int base=(a%p); while(b) { if(b&1) { res=(res*base)%p; } base=(base*base)%p; b>>=1; } return res; } struct Martix{ int n, m; int val[10][10]; void clear() { memset(val, 0, sizeof(val)); } void init() { clear(); for (int i = 0; i < n; i++) { val[i][i] = 1; } } Martix operator*(const Martix x) const { Martix Res; Res.n = n; Res.m = x.m; Res.clear(); for (int k = 0; k <m; k++) { for (int i = 0; i < Res.n; i++) { for (int j = 0; j < Res.m; j++) { Res.val[i][j]=(Res.val[i][j]+val[i][k]*x.val[k][j])%MOD; } } } return Res; } }A; Martix ppow(Martix Ad, int b) { Martix Res; Res=Ad; Res.init(); Martix Base = Ad; while (b) { if (b & 1) { Res = Res * Base; } Base = (Base * Base); b >>= 1; } return Res; } int F(int x) { Martix IDSY=ppow(A,x); int Res=0; for(int i=0;i<m;i++) { Res=(Res+IDSY.val[i][i])%MOD; } return Res; } vector<pair<int,int> >Rec; int Phi[205][205]; int Pri[205][205]; int Used[205]; int Res=0; int n; void dfs(int x) { if(x==Rec.size()) { int d=1; int phi=1; for(int i=0;i<Rec.size();i++) { d=(d*Pri[i][Used[i]]); phi=(phi*Phi[i][Used[i]])%MOD; } Res=(Res+((phi)%MOD*F((n/d)))%MOD)%MOD; return; } int Lim=Rec[x].second; for(int i=0;i<=Lim;i++) { Used[x]=i; dfs(x+1); } } int main() { scanf("%d",&t); while(t--) { Rec.clear(); scanf("%d %d %d",&n,&m,&k); A.clear(); A.n=m; A.m=m; for(int i=1;i<=A.n;i++) { for(int j=1;j<=A.n;j++) { A.val[i-1][j-1]=1; } } for(int i=1;i<=k;i++) { scanf("%d %d",&x,&y); A.val[x-1][y-1]=0; A.val[y-1][x-1]=0; } Res=0; int now=n; for(int d=2;d*d<=now;d++) { if(now%d==0) { int Tot=0; while(now%d==0) { now/=d; Tot++; } Rec.push_back(make_pair(d,Tot)); } } if(now>1) { Rec.push_back(make_pair(now,1)); } for(int i=0;i<Rec.size();i++) { int Lim=Rec[i].second; int p=Rec[i].first; Phi[i][0]=1; Pri[i][0]=1; for(int j=1;j<=Lim;j++) { Pri[i][j]=Pri[i][j-1]*p; Phi[i][j]=Pri[i][j]-Pri[i][j-1]; } } dfs(0); Res=(Res*Pow(n,MOD-2,MOD))%MOD; printf("%dn",Res); } return 0; } 
![洛谷 P11345 [KTSC 2023 R2] 基地简化 题解](http://www.itfaba.com/wp-content/themes/kemi/timthumb.php?src=http://www.itfaba.com/wp-content/themes/kemi/img/random/3.jpg&w=218&h=124&zc=1)
