若\(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|\)(不會證)
設\(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)|\)
\([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\)所在的等價類
再具體一點的例子就是環的著色問題
具體到染色問題,假設有\(m\)種顏色
則\(A^g=m^{c(g)}\),\(c(g)\)為\(g\)的不相交回圈個數
給定一個 \(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);
}
}
金妮的生日快到了。哈利波特正在為他的新女友準備生日禮物。禮物是一個由\(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;
}