听大佬们说了这么久Pólya定理,终于有时间把这个定理学习一下了。


置换(permutation)简单来说就是一个(全)排列,比如 \(1,2,3,4\) 的一个置换为 \(3,1,2,4\)。一般地,我们记 \(i\) 到 \(a_i(1<=i<=n)\) 的一个置换为

\[\left (
\begin{matrix}
1 & 2 & \cdots & n \\
a_1 & a_2 & \cdots & a_n
\end{matrix}
\right )
\]

可以发现,置换的本质是一一映射,所以我们可以将上面的置换简记为 \(f=\{a_1,a_2,\cdots,a_n\}\),其中 \(f(i)=a_i(1<=i<=n)\)。从这种映射的角度来看,置换是可以复合的。如果 \(f=\{a_1,a_2,\cdots,a_n\},g=\{b_1,b_2,\cdots,b_n\}\),我们称 \(fg=\{b_{a_1},b_{a_2},\cdots,b_{a_n}\}\) 为 \(f\) 和 \(g\) 的复合。它表示我们先将一个数 \(i\) 映射到 \(f(i)\),再映射到 \(g(f(i))\)。比如,\(f=\{1,3,4,2\},g=\{3,2,1,4\}\),则 \(fg=\{3,1,4,2\}\),它表示 \(2\) 先映射到 \(f(2)=3\),这个 \(3\) 再映射到 \(g(3)=1\),所以总的来说,\(fg(2)=g(f(2))=1\)。

循环(permutation cycle)是一类特殊的置换,它表示一些元素有次序地交换位置。通常地,我们记置换\(\left(\begin{matrix} a_1 & a_2 & \cdots & a_{n-1} & a_n \\ a_2 & a_3 & \cdots & a_n & a_1\end{matrix}\right)\)的循环为 \((a_1,a_2,\cdots,a_n)\)。与置换类似,循环也有乘积。我们常用循环的乘积来表示置换,如\(\left(\begin{matrix} 1 & 2 & \cdots & k & k+1 & \cdots & n \\ 2 & 3 & \cdots & 1 & k+2 & \cdots & k+1\end{matrix}\right) = (1,2,\cdots,k)(k+1,\cdots,n)\)。虽然置换乘法是不可交换的,但我们应当发现,对不相交的循环,不论用什么方式相乘,其结果总是一样的。

那么置换和Pólya定理有什么关系呢?我们通过一道题目来阐述。

题目(等价类计数问题)在 \(2\times 2\) 的方格中,我们将每个方格涂成黑白两色。如果允许旋转,一共会有多少种方案?

分析 我们先考虑没有旋转的所有情况。有以下 \(16\) 种:

置换及P&#243;lya定理-LMLPHP

令方格的四个格子分别为 \(A_1,A_2,A_3,A_4\),分别对应坐标系中的四个象限。那么我们可以定义(顺时针)旋转集合 \(R=\{\) 旋转0°, 旋转90°, 旋转180°, 旋转270° \(\}=\{(A_1)(A_2)(A_3)(A_4),(A_1,A_2,A_3,A_4),(A_1,A_3)(A_2,A_4),(A_4,A_3,A_2,A_1)\}\)。通过这个集合我们可以定义一个等价关系:(顺时针)旋转后相等。我们将所有等价的元素分成一个集合,称之为一个等价类,则现在题目要求的就是\(R\)所定义的不同的等价类的个数。我们有结论:

引理(Burnside引理):如果对于一个操作集合 \(R\) 中的操作 \(f\),某个元素 \(s\) 在 \(f\) 操作后不变,则称 \(s\) 为 \(f\) 的不动点。若将 \(f\) 的不动点数目记为 \(C(f)\),则由 \(R\) 定义的所有等价类数量为所有 \(C(f)\)的平均值。

那么本题中就有所有等价类数目为 \((16 + 2 + 4 + 2) / 4 = 6\) 个。

现在来考虑如何求 \(C(f)\)。不难发现,如果一个操作 \(f\) 被分解为 \(m(f)\) 个循环,则每个循环内元素所染的颜色均相同。那么有 \(C(f)=2^{m(f)}\)。推广开来,如果不止 \(2\) 种颜色,而是 \(k\) 种,则有 \(C(f)=k^{m(f)}\)。代回Burnside引理就得到Pólya定理。

定理(Pólya定理):如果对于一个操作集合 \(R\) 中的操作 \(f\),可被分解为 \(m(f)\) 个循环,且每个元素最多有 \(k\) 种颜色,则由 \(R\) 定义的所有等价类数量为所有 \(k^{m(f)}\)的平均值。

例题 Pólya定理模板 题目大意:\(t(t<=10^3)\) 组数据,每组数据给定一个有 \(n(n<=10^9)\) 个点的环,染 \(n\) 种颜色,在只考虑旋转的情况下,有多少种不同的染色数?

分析 如果旋转 \(i\) 个距离,则 \(0,i,2i,\cdots\) 构成一个长度为 \(n/gcd(i,n)\) 的循环。一共有 \(n/(n/gcd(i,n))=gcd(i,n)\) 个循环,因此答案为 \(\frac1n\sum_{i=1}^n n^{gcd(i,n)}\)。容易发现,这样做肯定是要超时的。所以我们愉快地推一波式子。

\[\begin{aligned}
& \frac1n\sum_{i=1}^n n^{gcd(i,n)} \\
&=\frac1n\sum_{d|n}n^d\sum_{i=1}^n[gcd(i,n)=d] \\
&=\frac1n\sum_{d|n}n^d\sum_{i=1}^{\frac{n}{d}}[gcd(i\cdot d,n)=d] \\
&=\frac1n\sum_{d|n}n^d\sum_{i=1}^{\frac{n}{d}}[gcd(i,n/d)=1] \\
&=\frac1n\sum_{d|n}n^d\varphi(\frac{n}{d})
\end{aligned}
\]

然后就可以瞎搞暴力了。

#include<bits/stdc++.h>
using namespace std; typedef long ll;
const ll mod = 1E+9 + 7; ll T, n, ans; ll Phi(ll x)
{
ll res = 1;
for(ll i = 2; i * i <= x; ++i) {
if(!(x % i)) {
x /= i, res = res * (i - 1) % mod;
while(!(x % i)) x /= i, res = res * i % mod;
}
} if(x != 1) res = res * (x - 1) % mod;
return res;
} ll QuickPow(ll a, ll b)
{
ll res = 1; a %= mod;
while(b) {
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
} int main()
{
scanf("%lld", &T);
while(T--) {
ans = 0; scanf("%lld", &n);
for(ll i = 1; i * i <= n; ++i) {
if(n % i) continue; ans = (ans + (Phi(n / i) * QuickPow(n, i - 1))) % mod;
if(i * i != n) ans = (ans + (Phi(i) * QuickPow(n, n / i - 1))) % mod;
}
printf("%lld\n", ans);
}
}
05-16 22:17