Pólya 定理

Pólya 定理

P4980 【模板】Pólya 定理

不能通过旋转与别的染色方案相同。

群

定义集合 $G$ 的作用余集合 $G$ 的二元运算 $\times$。

群记作：$(G,\times)$，有以下性质：

• 封闭性：

$$\exists a,b,a\in G,b\in G\Rightarrow a\times b\in G$$

• 结合律：

$$\forall a,b,c\Rightarrow (a\times b)\times c=a\times (b\times c)$$

• 单位元唯一

设单位元 $e$。

$$\exists e\in G,\forall a \in G\Rightarrow a\times e=e\times a=a$$

• 逆元

$$\forall a\in G,\exists a^{'}\in G\Rightarrow a\times a^{'}=a^{'}\times a=e$$

子群

如果 $H$ 为 $G$ 的一个子集，且 $(H,\times)$ 构成一个群，那么称 $(H,\times )$ 为 $(G,\times )$ 的一个子群，简记为 $H\le G$。

如果 $G$ 是一个群，$H$ 为其一个子群，且 $g\in G$，那么：

$gH=g\times h,h\in H$，称 $H$ 在 $G$ 内关于 $g$ 的左陪集。

$Hg=h\times g,h\in H$，称 $H$ 在 $G$ 内关于 $g$ 的右陪集。

• 陪集的一些性质（下面的是右陪集）：

• $$\forall g\in G,|H|=|Hg|$$
• $$\forall g\in G,g\in Hg$$
• $$Hg=H\Leftrightarrow g\in H$$
• $$Ha=Hb\Leftrightarrow a\times b^{-1}\in H$$
• $$Ha\cap Hb\not=\varnothing\rightarrow Ha=Hb$$

• $H$ 的全体右陪集的并为 $G$。

陪集是一种划分，构成了群元素的一种分类，每个元素属于一个类且只属于一个类。

群作用

定义：对于一个集合 $M$ 和群 $G$。

若给定了一个二元函数 $\varphi(x,k)$ 其中 $x$ 为群中的元素，$k$ 为集合元素，且有：

$$\varphi(x,\varphi(y,k))=\varphi(x\times y,k)$$

则称群 $G$ 作用于集合 $M$。

拉格朗日定理

• $|G|=|H|·[G:H]$，其中 $[G:H]$ 为子群的 $H$ 在群 $G$ 中不同陪集的个数，称 $H$ 在 $G$ 的指数。

• 传递性：$[G:H][H:K]=[G:K]$

• 对于有限集合，$K\le H,H\le G$，那么有

$$|G|=|H|·[G:H],|H|=|K|·[H:K]$$ $$\rightarrow [G:H][H:K]=\frac{|G|}{|H|}·\frac{|H|}{|K|}=\frac{|G|}{|K|}=[G:K]$$

• 对于无限集合，同样 $G$ 关于 $H$ 的右陪集的个数 $·H$ 关于 $K$ 的右陪集的个数 $=G$ 关于 $K$ 的右陪集的个数。

置换

置换群就是一些置换的集合：

$$\begin{gathered} \begin{pmatrix} 1&2&3&4\\ 2&3&1&4 \end{pmatrix} \end{gathered}$$

是一个置换，但不是一个置换群，置换只与每列的相对字符有关，与列顺序天关，例如：

$$\begin{gathered} \begin{pmatrix} 1&2&3&4\\ 2&3&1&4 \end{pmatrix} \end{gathered} = \begin{gathered} \begin{pmatrix} 2&4&3&1\\ 3&4&1&2 \end{pmatrix} \end{gathered}$$

现在有：

$$(7,5,3,9)$$

经过上边的置换变成：

$$(3,7,5,9)$$

可以将置换的第一行看成序列的下标，第二行看成变换后的下标，所以一般将第一行先变换成 $1,2,3,…$。

置换群就是一个将置换作为元素的群。

轨道-稳定子定理

• 轨道：

考虑一个作用在 $X$ 上的群 $G$。$X$ 中的一个元素 $x$ 的轨道就是 $x$ 通过 $G$ 中的元素可以转移的元素集合。$x$ 的轨迹被几位 $G(x)$，定义 $g(x)$ 表示群 $G$ 元素 $g$ 作用于 $x$ 的群作用的返回值，$g(x)=\phi(g,x)$。

• 稳定子

定义：$G^x={g\mid g\in G,g(x)=x}$

人话： 群 $G$ 中的满足 $g(x)=x$ 的所有元素 $g$ 所构成的集合。

对于：

$$\begin{gathered} \begin{pmatrix} 1&1\\ 0&0 \end{pmatrix} \end{gathered}$$

这些：

$$\begin{gathered} \begin{pmatrix} 1&0\\ 1&0 \end{pmatrix} & \begin{pmatrix} 0&0\\ 1&1 \end{pmatrix} & \begin{pmatrix} 0&1\\ 0&1 \end{pmatrix} \end{gathered}$$

旋转后和上边是一种情况。如果根据题目要求，就要判重判掉。

对于：

$$\begin{gathered} \begin{pmatrix} 1&1\\ 0&0 \end{pmatrix} \end{gathered}$$

而言，他的稳定子 $G^x$ 为 $\{ \text{顺时针旋转 }0^{\circ}\}$

发现轨道大小和稳定子乘积为 $4$，刚好是群 $G$ 的大小。

• 轨道-稳定子定理：

$$|G^x|\times |G(x)|=|G|$$

$G^x$ 是 $G$ 的一个子群，根据拉格朗日定理：

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

只用证明 $[G:G^x]=|G(x)|$

每一个 $g(x)$ 对应一个 $[G:G^x]$ 中的一个左陪集（或右陪集）即可。

设 $f(x)=g(x)$，那么：$f\times g^{-1}=x=e(x)\in G^x$，由于陪集的性质 $f\times G^x=g\times G^x$，所以相同的 $f(x)$ 可以对应相同的陪集。

同样：$f\times G^x=g\times G^x\Leftrightarrow f(x)=g(x)$

现在对于每一个 $g(x)$ 让 $g\times G^x$ 表示它对应的陪集，不难发现相同的 $g(x)$ 对应着相同的陪集。

$Burnside$ 引理

设 $G={a_1,a_2,…,a_n}$ 是目标集 $[1,n]$ 上的置换群。每个置换都写成不相交循环的乘积（下面解释）。$f(a_k)$ 是置换 $a_k$ 的作用下位置前后不变的点的个数（例如上面置换中的 $4$）。通过上述操作置换的变换操作后可以相等的元素属于同一个等价类。若 $G$ 将 $[1,n]$ 划分成 $L$ 个等价类，则：等几类个数为

$$L=\frac{1}{|G|}\times \sum_{i=1}^n{f(a_i)}$$

或者写成（不进行划分，直接找元素）：

$$L=\frac{1}{|G|}\times \sum_{ai\in G}{f(a_i)}$$

置换写成不相交循环的乘积，假设现在有一个置换：

$$\begin{gathered} \begin{pmatrix} 1&2&3&4&5&6&7\\ 3&7&1&5&4&2&6 \end{pmatrix} = (1&3)(4&5)(2&6&7) \end{gathered}$$

不难发现在置换中 $1,3$ 是一个“循环”，同样 $4,5$ 也是，$2,6,7$ 同样是。我们就可以根据这些“循环”将他们写成乘积的形式。

• Pólya 定理的公式：

记 $\lambda(a_i)$ 为置换 $a_i$ 的循环数量：

$$L=\frac{1}{|G|}\sum_{a_i\in G}{m^{\lambda(a_i)}}$$

变形：设 $\lambda_k{(a_i)}$ 是置换 $a_i$ 中长度为 $k$ 的循环的数量：

$$L=\frac{1}{|G|}\sum_{a_i\in G}{m^{\lambda_1(a_i)+\lambda_2(a_i)+…+\lambda_n(a_i)}}$$

• 证明 $Burnside$ 引理：

由于每个元素属于一个轨道，轨道内部在群 $G$ 的作用下互达（陪集的性质）：

$|S/G|$ 代表有一个 $G$ 的置换群，其作用于 $S$（其实就是上面用的 $L$）。

$$L=\sum_{a_i\in G}{\frac{1}{[G:G^x]}}$$

轨道-稳定子定理（还有在拉格朗日的推导）：

$$[G:G^x]=\frac{G}{|G^x|}$$ $$L=\sum_{a_i\in G}{\frac{G^x}{G}}$$

将 $G$ 提出来：

$$L=\frac{1}{|G|}\sum_{a_i\in G}{G^x}$$

这里的 $G^x$ 是 $G$ 的子群（见上文），将它当成上文的 $f(x)$ 即可。

解题

本质不同的 $n$ 个点的环可以看成群 $G$ 为：

$$\text{ 旋转 $0$ 个，旋转 $1$ 个，$…$，旋转 $n-1$ 个。}$$

这些置换作用下的得到的等价类的数量。

设集合 $M$ 为 $\{1\rightarrow n\}$ 的所有可能的排列的初始的环。

$$ans=\frac{1}{|G|}\sum_{a_i\in G}{M^{\lambda(a_i)}}$$

对于旋转 $k$ 个，一个元素的不动点等价与存在一个长度为 $a$ 的循环，满足 $a\mid k$，又因为对于循环节 $a$，必定存在 $a\mid n$，那么一个循环长度就是 $\gcd(k,n)$。

每个子串的前 $\gcd(k,n)$ 是任意取得，一共有 $n$ 个点，贡献为 $n^{\gcd(k,n)}$。

$$ans=\frac{1}{n}\sum_{k=1}^n{n^{\gcd(k,n)}}$$

不难发现，将其中的是 $n$ 的因子的部分提出来，分开处理：

$$ans=\frac{1}{n}\sum_{d\mid n}{n^d}\times \sum_{k=1}^{\frac{n}{d}}{[\gcd(k,\frac{n}{d})==1]}$$ $$\sum_{k=1}^{\frac{n}{d}}[\gcd(k,\frac{n}{d})==1]$$

代表从 $1$ 到 $\frac{n}{d}$ 和 $\frac{n}{d}$ 互质的数有多少，也就是欧拉函数。

$$=\frac{1}{n}\sum_{d\mid n}{n^d\varphi(\frac{n}{d})}$$

代码

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<map> 
#include<unordered_map>
using namespace std;
long long r_r(){//快读 
  long long k=0,f=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(isdigit(c)){
    k=(k<<1)+(k<<3)+(c^48);
    c=getchar();
  }
  return k*f;
}
const int o_o=5e6+10;
const long long m_d=1e9+7; 
long long t,n; 
long long k_m(long long a,long long b){//快速幂 
  long long r_s=1;
  while(b){
    if(b&1)r_s=a*r_s%m_d;
    a=(a*a)%m_d;
    b>>=1;
  }
  return r_s;
}
long long p_i(long long x){//欧拉函数 
  long long a_s=x;
  for(long long i=2;i*i<=x;i++){
    if(x%i)continue;
    a_s-=a_s/i;
    while(!(x%i))x/=i;
  }
  if(x>1)a_s-=a_s/x;
  return a_s;
}
int main(){
  long long t=r_r(); 
  while(t--){
    long long n=r_r();
    long long a_s=0; 
    for(long long i=1;i*i<=n;++i){
      if(n%i)continue;//不是因数 
      long long p_1=p_i(i);//计算欧拉函数 
      long long f_1=k_m(n,n/i);//快速幂 
      f_1=f_1*p_1%m_d;//计算贡献的权值 
      a_s=(a_s+f_1)%m_d;//累计 
      if(i*i!=n){//n 不是完全平方数（防止一个因数计算两遍） 
        
        //另一部分因数（n/i）比根号 n 大的部分的因数 
        long long p_2=p_i(n/i);//欧拉函数 
        long long f_2=k_m(n,i);//快速幂 
        f_2=f_2*p_2%m_d;//计算贡献的权值 
        a_s=(a_s+f_2)%m_d;//累计 
      }
    }
    printf("%lld\n",a_s*k_m(n,m_d-2)%m_d);//输出，记得乘上除数的逆元 
  }
  return 0;
}