群
一些基础
子群
若\(H\)是\(G\)的子集且\(<H,op>\)为群,则\(<H,op>\)为\(<G,op>\)的子群
则\(H\)既满足封闭性且求逆封闭,\(\forall a,b\in H,ab\in H,a^{-1}\in H\)
等价于\(\forall a,b\in H,ab^{-1}\in H\)
一些特殊特殊的子群:
生成子群:\(a\in G\),则\(<\{a^i,i\in Z\},op>\)称为生成子群
正规化子:\(a\in G\),则\(<\{x|ax=xa,x\in G>\)称为正规化子,记为\(N(a)\)
共轭子群:\(a\in G,H\)为\(G\)的子群,则\(xHx^{-1}\)称为\(H\)的共轭子群
等价类
等价关系:满足自反性\(a=a\),对称性\(a=b\Leftrightarrow b=a\),传递性\(a=b,b=c\Leftrightarrow a=c\)(\(=\)代表的是等价关系)
等价类:\(x\)的等价类\([x]_R=\{y|<x,y>\in R\}\),\(R\)是满足某种等价关系两个元素所有集合
可以认为是把等价关系看作边,\([x]_R\)是\(x\)所在联通块的大小
商集:\([A/R]\)指在以\(R\)为等价关系时等价类的集合
陪集
陪集分为右陪集与左陪集,两个没区别
对于\(a\in G\),\(H\)是\(G\)的子群,称\(Ha=\{ha|h\in H\}\)为\(H\)的右陪集
如果\(H\)为有限集,则\(|Ha|=|H|\)(不会证)
Lagrange定理
设\(H\)为\(G\)的子群,则\(|G|\)为\(|H|\)的倍数
考虑用陪集分解群
首先有个结论,\(\forall a,b\in G,H\)为\(G\)的子群,\(a\in Hb\Leftrightarrow Ha=Hb\Leftrightarrow ab^{-1}\in H\)
若已知\(a\in Hb\),则\(a=h_1b,h_1\in H\),\(\forall h_2\in H\),\(h_2a=h_2h_1b\),且\(h_2h_1\in H\)
则\(Ha\subseteq Hb\),反过来同理的\(Hb\subseteq Ha\),即\(Ha=Hb\)
若已知\(Ha=Hb\),则\(\exist h_1,h_2\in H,h_1a=h_2b\),\(ab^{-1}=h_1^{-1}h_2\in H\)
若已知\(ab^{-1}\in H\),则\(ab^{-1}=h\in H\),则\(a=hb\in Hb\)
如果将\(Ha=Hb\)视为一种等价关系,\(H\)一定单独是一个等价类
若\(a\notin H\),则\(Ha\not=He\),即\(a\)一定不与\(e\)在同一等价类
又\(|Ha|=|H|\),所以所有等价类大小相同
即\(\dfrac{|G|}{|H|}=|[G/R]|,R=\{<a,b>,Ha=Hb\}\)
由此还可以得到共轭类分解
共轭关系也是一种等价关系,将\(a\in G\),所有与\(a\)共轭的\(b\)形成的集合称为共轭类
\(a\)所在的共轭类大小为\(\dfrac{|G|}{|N(a)|}\)
令\(x,y\in G,xax^{-1}=yay^{-1}\)
\(xa=yay^{-1}x\Rightarrow y^{-1}xa=ay^{-1}x\Rightarrow y^{-1}x\in 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\)的置换群,\(a\in A\)
定义\(G^a=\{g|g(a)=a,g\in G \}\),称为稳定子群
\(G(a)=\{g(a),g\in G \}\),称为轨道
\(|G|=|G(a)|\times|G^a|\),证明如下
设\(x,y\in G\),且\(x(a)=y(a)\),则\(\Leftrightarrow a=x^{-1}(y(a))\Leftrightarrow x^{-1}y\in G^a\Leftrightarrow xG^a=yG^a\)
将\(G\)以\(G^a\)陪集分解,则当\(x(a)=y(a)\)时\(x,y\)属于同一等价类
考虑等价类的个数即为有多少个不同的\(x(a)\)即为\(|G(a)|\)
Burnside 引理
\([A/G]=\dfrac{1}{|G|}\sum\limits_{g\in G}[A^g]\),\(A^g\)的定义与\(G^a\)类似,就是\(A^g=\{a|g(a)=a,a\in A \}\)
\(|G^a|=\dfrac{|G|}{|G(a)|}\)，两边同时求和
\(\sum\limits_{a\in A}|G^a|=\sum\limits_{a\in A}\dfrac{|G|}{|G(a)|}=|G|\sum\limits_{a\in A}\dfrac{1}{|G(a)|}\)
观察\(\sum\limits_{a\in A}\dfrac{1}{|G(a)|}\)，本质为轨道个数(每一个\(a\)所在的等价类大小分之\(1\)求和就是等价类的个数)=\([A/G]\)
\(\sum\limits_{a\in A}|G^a|=\sum\limits_{g\in G}[A^g]=|G|\times|[A/G]|\)
即\([A/G]=\dfrac{1}{|G|}\sum\limits_{g\in 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|}\sum\limits_{g\in G} n^{c(g)}=\dfrac{1}{n}\sum\limits_{i=1}^nn^{gcd(i,n)}\)
令\(f(x)=n^x\)
\([A/G]=\dfrac{1}{n}\sum\limits_{i=1}^nf(gcd(i,n))=\dfrac{1}{n}\sum\limits_{d|n}f(d)\sum\limits_{i=1}[gcd(i,n)=d]=\dfrac{1}{n}\sum\limits_{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("%d\n",Res);
}
}
Magic Bracelet
金妮的生日快到了。哈利波特正在为他的新女友准备生日礼物。礼物是一个由\(n\)颗魔法珠组成的魔法手镯。有\(m\)种不同的魔珠。每种珠子都有其独特的特征。将许多珠子串在一起，将制作一个漂亮的圆形魔法手镯。正如哈利波特的朋友赫敏所指出的那样，某些种类的珠子会相互作用并爆炸，哈利波特必须非常小心地确保这些对的珠子不会并排串在一起,有无数种珠子。如果忽略围绕手镯中心旋转产生的重复，哈利能制作多少种不同的手镯？找到取模 \(9973\) 的答案。
同样定义\(G\)为轮换\(i\)次的置换群,但由于不能随便染色,所以不能用\(Pólya\)定理
\([A/G]=\dfrac{1}{|G|}\sum\limits_{g\in G}|A^g|\)
瓶颈在于计算\(|A^g|\)
我们将\(g\)拆分成不同的循环,这些循环的内部的点颜色是相同的且每个循环大小相同,问题是不同循环之间的关系
如果我们把一个循环看成一个点,再将和他有关系的连边,最后连出还是一个环
我们可以考虑只在这个环上计算答案
设\(f(x)\)为长度为\(x\)的环时的答案
\([A/G]=\dfrac{1}{n}\sum\limits_{g\in G}|A^g|=\dfrac{1}{n}\sum\limits_{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("%d\n",Res);
}
return 0;
}