Polya 定理入门[Burnside引理,Polya定理,欧拉函数]

$这篇 b l o g 重点讨论 P o l y a 的应用, 更详细的证明请百度 .$

$B u r n s i d e 引理$

$L = \frac{1}{∣ G ∣} <munderover> \sum i = 1 ∣ G ∣ </munderover> D (a_{i})$

$L$ : 本质不同的方案数.
$G$ : 置换群集合.
$a_{i}$ : 置换群中的第 $i$ 个置换.
$D (a_{i})$ : 进行 $a_{i}$ 这个置换, 状态不会变化的方案数量.

该引理与下方内容没有太大关系, 可以暂时忽略.

$P r o b l e m$ 链接
有 $N$ 个石子围成一圈, 使用 $M$ 种颜色染色, 求有多少种本质不同的方案.

借此问题引入 $P o l y a 定理$ $↓$

$P o l y a 定理$

$L = \frac{1}{∣ G ∣} <munderover> \sum i = 1 ∣ G ∣ </munderover> M^{C (g_{i})}$

先丢出公式.

这道题的 置换群 $G$ : 转 $0$ 次, 转 $1$ 次 …转 $N - 1$ 次, (皆为顺时针转动).
若满足旋转 $k$ 个位置, 状态和原来相同, 那么 $i$ 位置颜色等于 $(i + k) % N$ 位置颜***r> 旋转 $t$ 次, 仍和原来位置相同, 即 $i$ 位置与 $(i + t * k) % N$ 位置颜色相同,
则 $i$ 旋转 $t$ 个 $k$ 次, 一定能回到原来位置, 即可以无限旋转,
所以 $i$ 就与所有 $(i + t * k) % N$ 位置呈现一个封闭的 $<mstyle mathcolor="red"> 循环节 </mstyle>$ .
设转了 $t$ 次后, 第一次回到 $i$ 位置, 则
$t * k = l c m (k, N) = \frac{k * N}{g c d (k, N)}$ ,
$∴ t = \frac{N}{g c d (k, N)}$ ,

$t$ 为 $<mstyle mathcolor="red"> 循环节 </mstyle>$ 长度, 则 $<mstyle mathcolor="red"> 循环节 </mstyle>$ 数量为 $\frac{N}{t} = g c d (k, N)$ .

公式中颜色的数量为 $M$ ; 在 $g_{i}$ 置换下, 有 $C (g_{i})$ 个 $<mstyle mathcolor="red"> 循环节 </mstyle>$ .

此题中 $C (g_{i}) = g c d (k, N)$ , $∴ A n s = L = \frac{1}{N} <munderover> \sum k = 0 N - 1 </munderover> M^{g c d (k, N)}$

$拓展 1$

假如上题增加 $<mstyle mathcolor="red"> 对称同构 </mstyle>$ , 则意味着原先的两个不同方案对称时计为一个方案,
按 $N$ 的奇偶分类讨论:

$N$ 为奇数, 对称轴上有一个点, 循环节个数为 $\frac{N + 1}{2}$ , 总共有 $N$ 个对称轴置换, 则对答案贡献为 $\frac{N * M^{\frac{N + 1}{2}}}{2 N}$
最后的答案为 $A n s = L = \frac{1}{2 N} (<munderover> \sum k = 0 N - 1 </munderover> M^{g c d (k, N)} + N * M^{\frac{N + 1}{2}})$
$N$ 为偶数, 对称轴上可以没有点, 也可以有两个点, 两种对称轴都有 $\frac{N}{2}$ 种, 总共有 $N$ 个对称轴置换,
对称轴上无点时, 循环节个数为 $\frac{N}{2}$ , 对答案贡献为 $\frac{M^{\frac{N}{2}}}{2 N}$ ,总贡献为 $\frac{\frac{N}{2} * M^{\frac{N}{2}}}{2 N}$ .
对称轴上有点时, 循环节个数为 $\frac{N}{2} + 1$ , 对答案贡献为 $\frac{M^{\frac{N}{2} + 1}}{2 N}$ , 总贡献为 $\frac{\frac{N}{2} * M^{\frac{N}{2} + 1}}{2 N}$ .

所以最后的答案为
$A n s = L = \frac{1}{2 N} (<munderover> \sum k = 0 N - 1 </munderover> M^{g c d (k, N)} + \frac{N}{2} * M^{\frac{N}{2}} + \frac{N}{2} * M^{\frac{N}{2} + 1})$

$拓展 2$

若 $<mstyle mathcolor="red"> N < = 1 0^{9} </mstyle>$ , $O (N)$ 计算下式会 $T L E$ , 需要更快的办法,
$A n s = L = \frac{1}{N} <munderover> \sum k = 0 N - 1 </munderover> M^{g c d (k, N)}$

由于 $g c d (k, N) ∣ N$ , 而 $N$ 的约数不会超过 $2 \sqrt{N}$ 个,
考虑枚举 $d$ , $(d ∣ N)$
则就只需统计 $g c d (k, N) = d$ 的 $k$ 的个数.
$d = g c d (k, N) = g c d (d * t, d * \frac{N}{d})$
则 $t$ 与 $\frac{N}{d}$ 互质, 即 $<mstyle mathcolor="red"> g c d (t, \frac{N}{d}) = 1 </mstyle>$ .
$∴ <mstyle mathcolor="red"> φ (\frac{N}{d}) </mstyle>$ 即为 $g c d (k, N) = d$ 的 $k$ 的个数.

于是 $A n s = L = \frac{1}{N} <munder> \sum d ∣ N </munder> φ (\frac{N}{d}) * M^{d}$
.

$如何求解 φ (x) ?$
根据定义: $φ (x) = x <munder> \prod p_{i} ∣ x </munder> (1 - \frac{1}{p_{i}})$
通分得: $φ (x) = x \prod_{p_{i} ∣ x} \frac{p_{i} - 1}{p_{i}}$
按上式实现, 时间复杂度小于 $O (\sqrt{N})$ , 均摊 $O (l o g N) ?$
这里给出求解函数,

int Get_phi(int x){
    int s = x;
    for(int i = 2; i*i <= x; i ++)
        if(x % i == 0){ //找到一个质因数
            s = s/i*(i-1);
            while(x%i == 0) x /= i;
        }
    if(x > 1) s = s/x*(x-1);	//不可能出现两个大于 sqrt(N) 的质因数, 所以只可能剩下一个, 处理掉就好 .
    return s;
}

所以 $O (\sqrt{N}), O (l o g N)$ 分别求出所有约数 $d$ 和 $φ (\frac{N}{d})$ 即可, 时间复杂度 $O (\sqrt{N} l o g N)$ .

$C o d e$

#include<bits/stdc++.h>
#define reg register

const int mod = 1e9 + 7;

int T;
int N;

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

int KSM(int a, int b){
        int s = 1; a %= mod;
        while(b){
                if(b & 1) s = 1ll*s*a % mod;
                a = 1ll*a*a % mod, b >>= 1;
        }
        return s;
}

void Work(){
        scanf("%d", &N);
        int Ans = 0;
        int lim = sqrt(N);
        for(reg int d = 1; d <= lim; d ++){
                if(N % d) continue ;
                Ans = ( 1ll*Ans + (1ll*phi(N/d) * KSM(N, d) % mod) ) % mod;
                int d_2 = N / d;
                if(d_2 == d) continue ;
                Ans = ( 1ll*Ans + (1ll*phi(N/d_2) * KSM(N, d_2) % mod) ) % mod;
        }
        printf("%d\n", (1ll*Ans*KSM(N, mod-2)) % mod);
}

int main(){
        scanf("%d", &T);
        while(T --) Work();
        return 0;
}

$例题$

更多例题请戳这里 .

Polya 定理入门[Burnside引理,Polya定理,欧拉函数]

B u r n s i d e 引 理 Burnside引理 Burnside引理

借此问题引入 P o l y a 定 理 Polya定理 Polya定理 ↓ ↓ ↓

P o l y a 定 理 Polya定理 Polya定理

拓 展 1 拓展 1 拓展1