Polya 定理

一.群

1.群的定义

对于一个集合 \(S\) 和定义在这个集合上的二元运算 \(*\) , 满足：

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

• 结合律。 \(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 \}\)。

同样可以定义右陪集。

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

---

陪集的性质：

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\) 不同陪集的数量

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

有：

\[|H|×[G:H]=|G| \]

证明：由陪集的性质 1、5、6 显然。

三.置换群

1.置换

对于集合 \(S=\{a_1,a_2 \dots a_n\}\) , 一个置换 \(f\) 可表示为：

\[f=\begin{pmatrix} a_1,a_2,\dots,a_n\a_{p_1},a_{p_2},\dots,a_{p_n} \end{pmatrix}\]

\(p\) 为 \(1\sim n\) 的排列，意义为将 \(a_i\) 映射为 \(a_{p_i}\)。

\[f=\begin{pmatrix} a_{p_1},a_{p_2},\dots,a_{p_n}\a_{q_1},a_{q_2},\dots,a_{q_n} \end{pmatrix}, g=\begin{pmatrix} a_1,a_2,\dots,a_n\a_{p_1},a_{p_2},\dots,a_{p_n} \end{pmatrix}\]

\[f \times g=f(g(x))=\begin{pmatrix} a_1,a_2,\dots,a_n\a_{q_1},a_{q_2},\dots,a_{q_n} \end{pmatrix}\]

称为置换的乘法。

2.循环置换

一种特殊的置换，其中：

\[f=(a_1,a_2,\dots,a_n)=\begin{pmatrix} a_1,a_2,\dots,a_n\a_2,a_3,\dots,a_1 \end{pmatrix}\]

任意一个置换都可以表示为若干不相交的循环置换的乘积，例如

\[\begin{pmatrix}a_1,a_2,a_3,a_4,a_5\\ a_3,a_1,a_2,a_5,a_4\end{pmatrix}=(a_1,a_3,a_2) \times (a_4,a_5) \]

将一个置换 \(f\) 拆分的循环置换个数记为 \(c(f)\)

3.置换群

若 \(S\) 包含所有的 \(n!\) 个不同 \(n\) 元置换，\(G(S,\times)\) 为一个群，证明如下：

• 封闭性。 两个 \(n\) 元置换的乘积仍为 \(n\) 元置换，包含于 \(S\)。
• 结合律。置换的乘法有结合律。
• 单位元。置换 \(\begin{pmatrix}a_1,a_2,\dots,a_n\\ a_1,a_2,\dots,a_n\end{pmatrix}\)，也称恒等置换。
• 逆元。上下两行交换即可。

\(G\) 的子群称作置换群。

四.Burnsied 引理 和 Pólya 定理

1.轨道稳定子定理

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

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

\(x\) 的稳定子：\(G^x=\{ g \in G| g(x)=x\}\)

这里 \(g(x)\) 为群作用的函数，例如上文提到的置换。

---

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

   证明：

   • 封闭性。 \(f(x)=x,g(x)=x,f \times g=f(g(x))=x\),所以 \(f \times g \in G^x\)
   • 结合律。显然。
   • 单位元。\(\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\) 对应不同的陪集。

   所以对于 \(G(x)\) 中的 \(g\) , 构造对应陪集为 \(gG^x\)。

   感觉在伪证。

---

轨道稳定子定理：

\[|G(x)| \times |G^x|= |G| \]

证明：

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

\[|G^x| \times [G:G^x]=|G| \]

由性质2得:

\[|G^x| \times |G(x)| = |G| \]

证毕。

\[\]

2.Burnside 引理

若一个置换群 \(G\) 作用于 \(X\) , \(X/G\) 表示在群 \(G\) 作用下 \(X\) 的所有等价类的集合。(注意每个等价类也是一个集合，若两个元素在 \(G\) 作用下可以转化则属于同一个等价类)

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

那么有：

\[|X/G|=\frac{1}{|G|}\sum_{g \in G} |X^g| \]

证明：

\[\begin{aligned} \sum_{g\in G} |X^g|&=\sum_{x \in X} |G^x| \ &=\sum_{x \in X} \frac{|G|}{|G(x)|} \ &=|G|\sum_{x \in X} \frac{1}{|G(x)|} \ &= |G|\sum_{Y \in X / G } \sum_{x \in Y} \frac{1}{|G(x)|} \ &= |G|\sum_{Y \in X / G } \sum_{x \in Y} \frac{1}{|Y|} \ &= |G|\sum_{Y \in X/G}1 \ &= |G||X/G| \end{aligned}\]

即：

\[|X/G|=\frac{1}{|G|}\sum_{g \in G} |X^g| \]

可以参考 oi-wiki 的例子。

3.Pólya 定理

\[|X/G|=\frac{1}{|G|}\sum_{g \in G} m^{c(g)} \]

证明：

由 burnside 引理发现，在 \(g\) 作用下的不动点的充要条件是每一个循环置换里元素同色。

那么式子就很显然了。

五.例题

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

首先置换群 \(G\) 包含的元素分别为: 旋转 \(1\) 个点,旋转 \(2\) 个点...旋转 \(n\) 个点

不难发现，旋转 \(k\) 个点的 \(c(g)=\gcd(n,k)\)，原因如下：

所有循环置换所包含的元素个数相同，均为 \(\frac{\text{lcm(n,k)}}{k}\)。(旋转次数/旋转步长)

那么循环置换的个数便为 \(\frac{n}{\frac{\text{lcm}(n,k)}{k}}=\gcd(n,k)\)

由 polya 定理得：

\[|X/G|=\frac{1}{n}\sum_{i=1}^n n^{\gcd(i,n)} \]

化简可得：

\[|X/G|=\frac{1}{n}\sum_{d|n}n^d\varphi(\frac{n}{d}) \]

直接计算即可，复杂度 \(\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;
}