一.群

1.群的定義

對于一個集合 \(S\) 和定義在這個集合上的二元運算 \(*\) , 滿足：

• 封閉性。 \(\forall a \in S,b \in S\) ，\(a*b \in S\)

• 結(jié)合律。 \(a*b*c=a*(b*c)\)

• 單位元。 \(\exists \epsilon \in S\) , \(a*\epsilon = \epsilon * a=a\)

• 逆元。 \(\forall a \in S\) , \(\exists b \in S\) , \(a * b = \epsilon\) , 記作 \(a'\)

那么稱 \((S,*)\) 為一個群。

值得注意的是，一個群的單位元和逆元都是唯一的。

2.子群

若 \(G(S,*)\) 為一個群，若 \(T \subseteq S\) ，且 \(H(T,*)\) 也為一個群，那么稱 \(H\) 為 \(G\) 的子群，記作 \(H \le G\)

3.陪集

左陪集：若群 \(H\) 為群 \(G\) 的一個子群，且對于 \(g \in G\)，\(gH=\{gh|h \in H \}\)。

同樣可以定義右陪集。

注意陪集可能不包含單位元，不一定是群。

陪集的性質(zhì)：

1. \(|H|=|gH|\)
2. \(g \in gH\)
3. \(gH=H \Leftrightarrow g \in H\)
4. \(aH=bH \Leftrightarrow a * b^{-1} \in H\)
5. \(aH \not= BH \Rightarrow aH \bigcap bH=\varnothing\)
6. \(\displaystyle \bigcup_{g \in G} gH={G}\)

二.拉格朗日定理

\([G:H]\): \(G\) 中 \(H\) 不同陪集的數(shù)量

\(G~/~H~\): \(G\) 中所有 \(H\) 的左陪集

有：

證明：由陪集的性質(zhì) 1、5、6 顯然。

三.置換群

1.置換

對于集合 \(S=\{a_1,a_2 \dots a_n\}\) , 一個置換 \(f\) 可表示為：

\(p\) 為 \(1\sim n\) 的排列，意義為將 \(a_i\) 映射為 \(a_{p_i}\)。

稱為置換的乘法。

2.循環(huán)置換

一種特殊的置換，其中：

任意一個置換都可以表示為若干不相交的循環(huán)置換的乘積，例如

將一個置換 \(f\) 拆分的循環(huán)置換個數(shù)記為 \(c(f)\)

3.置換群

若 \(S\) 包含所有的 \(n!\) 個不同 \(n\) 元置換，\(G(S,\times)\) 為一個群，證明如下：

• 封閉性。 兩個 \(n\) 元置換的乘積仍為 \(n\) 元置換，包含于 \(S\)。
• 結(jié)合律。置換的乘法有結(jié)合律。
• 單位元。置換 \(\begin{pmatrix}a_1,a_2,\dots,a_n\\ a_1,a_2,\dots,a_n\end{pmatrix}\)，也稱恒等置換。
• 逆元。上下兩行交換即可。

\(G\) 的子群稱作置換群。

四.Burnsied 引理 和 Pólya 定理

1.軌道穩(wěn)定子定理

對于作用在集合 \(X\) 上的群 \(G\) 和集合 \(X\) 的一個元素 \(x\)

\(x\) 的軌道：\(G(x)=\{ g(x) | g \in G\}\)

\(x\) 的穩(wěn)定子：\(G^x=\{ g \in G| g(x)=x\}\)

這里 \(g(x)\) 為群作用的函數(shù)，例如上文提到的置換。

1. \(G^x\) 為 \(G\) 的子群。

   證明：

   • 封閉性。 \(f(x)=x,g(x)=x,f \times g=f(g(x))=x\),所以 \(f \times g \in G^x\)
   • 結(jié)合律。顯然。
   • 單位元。\(\epsilon(x)=x\)，所以 \(\epsilon \in G^x\)
   • 逆元。\(\forall g \in G\)，因為 \(g\times g'=\epsilon\) , \(g(x)=\epsilon(x)=x\),所以 \(g'(x)=x\)，\(g'(x) \in G\)

2. \(|G(x)|=[G:G^x]\)

   證明：

   對于 \(f(x)=g(x)\) , \(f \times g^{-1}=\epsilon\)

   若有兩個 \(f(x)=g(x),f \times g^{-1} = x = \epsilon(x)\) ，所以 \(f \times g^{-1} \in G^x\) , \(\Rightarrow fG^x = gG^x\) , 反之亦然。

   即不同的 \(g\) 對應(yīng)不同的陪集。

   所以對于 \(G(x)\) 中的 \(g\) , 構(gòu)造對應(yīng)陪集為 \(gG^x\)。

   感覺在偽證。

軌道穩(wěn)定子定理：

證明：

因為 \(G^x\) 為 \(G\) 的子群，由拉格朗日定理得：

由性質(zhì)2得:

證畢。

2.Burnside 引理

若一個置換群 \(G\) 作用于 \(X\) , \(X/G\) 表示在群 \(G\) 作用下 \(X\) 的所有等價類的集合。(注意每個等價類也是一個集合，若兩個元素在 \(G\) 作用下可以轉(zhuǎn)化則屬于同一個等價類)

\(X^g\) 表示在 \(g\) 的作用下不變的 \(X\) 中元素的集合。

那么有：

證明：

即：

可以參考 oi-wiki 的例子。

3.Pólya 定理

證明：

由 burnside 引理發(fā)現(xiàn)，在 \(g\) 作用下的不動點的充要條件是每一個循環(huán)置換里元素同色。

那么式子就很顯然了。

五.例題

1.P4980 【模板】Pólya 定理

首先置換群 \(G\) 包含的元素分別為: 旋轉(zhuǎn) \(1\) 個點,旋轉(zhuǎn) \(2\) 個點...旋轉(zhuǎn) \(n\) 個點

不難發(fā)現(xiàn)，旋轉(zhuǎn) \(k\) 個點的 \(c(g)=\gcd(n,k)\)，原因如下：

所有循環(huán)置換所包含的元素個數(shù)相同，均為 \(\frac{\text{lcm(n,k)}}{k}\)。(旋轉(zhuǎn)次數(shù)/旋轉(zhuǎn)步長)

那么循環(huán)置換的個數(shù)便為 \(\frac{n}{\frac{\text{lcm}(n,k)}{k}}=\gcd(n,k)\)

由 polya 定理得：

化簡可得：

直接計算即可，復(fù)雜度 \(\mathcal{O(n^{\frac{3}{4}})}\)

#include <cstdio>

const int Mod = 1e9 + 7;
int Add( int x , int y ) { x += y; return x >= Mod ? x - Mod : x; }
int Sub( int x , int y ) { x -= y; return x < 0 ? x + Mod : x; }
int Mul( int x , int y ) { return 1ll * x * y % Mod; }
int Quick_pow( int x , int po ) { int Ans = 1; for( ; po ; po >>= 1 , x = Mul( x , x ) ) if( po & 1 ) Ans = Mul( Ans , x ); return Ans; }
int Inv( int x ) { return Quick_pow( x , Mod - 2 ); }
int Div( int x , int y ) { return 1ll * x * Inv( y ) % Mod; }


int phi( int n ) {
    int Ans = n;
    for( int i = 2 ; i * i <= n ; i ++ )
        if( n % i == 0 ) {
            Ans = Ans / i * ( i - 1 );
            while( n % i == 0 ) n /= i;
        }
    if( n > 1 ) Ans = Ans / n * ( n - 1 );
    return Ans;
}

int T , n;
int main( ) {
    scanf("%d",&T);
    while( T -- ) {
        scanf("%d",&n);
        int Ans = 0;
        for( int i = 1 ; i * i <= n ; i ++ )
            if( n % i == 0 ) {
                Ans = Add( Ans , Mul( Quick_pow( n , i ) , phi( n / i ) ) );
                if( i * i != n )
                    Ans = Add( Ans , Mul( Quick_pow( n , n / i ) , phi( i ) ) );
            }
        printf("%d\n", Div( Ans , n ) );
    }
    
    return 0;
}