Polya定理及应用
概念及定理
首先是群的概念：
设$G$是一个集合，$$是$G$上的二元运算，如果$(G,)$满足下面的条件：
- 封闭性：对于任何$a,b \in G$有$a*b \in G$;
- 结合律：对任何$a,b,c\in G$有$(a*b)c=a(b*c)$;
- 单位元：存在$e\in G$,使得对所有的$a\in G$,都有$a*e=e*a=a$;
- 逆元：对于每个元素$a\in G$,存在$x\in G$,使得$a*x=x*a=e$,这个时候记$x$为$a{-1}$，称为$a$的逆元，那么则称$(G,*)$为一个群。
例：$G={0,1,2,3,4....n-1}$，那么它在$\text{mod n}$加法下是一个群。
群元素的个数有限，称为有限群，且其中元素的个数称为阶，记为$|G|$,群元素的个数无限，称为无限群。
若对于群元素中的任意两个元素$a,b$都有$ab=ba$那么称$G$为交换群，简称Abel群。
置换：设$X$为一个有限集，$\pi$是$X$到$X$的一个一一变换，那么称$\pi$是$X$上的一个置换。
例：设$X={1,2,3,4....n}$,设$\pi$是$X$的一个变换，满足$\pi: 1\to a_1,2\to a_2,\dots n\to a_n$,其中$a_1,a_2\dots a_n$是X的一个排列，则称$\pi$是$X$上的一个置换。可将$\pi$记为:
$$ \begin{array}{|c|c|c|c|c|}\hline 1 & 2 & 3 & \dots & n \ \hline a_1 & a_2 & a_3 & \dots & a_n \ \hline \end{array} $$
同一置换用这样的表示法有$n!$种，但其对应的关系不变。 假设循环$\pi$只这样一个置换，满足$\pi: a_1\to a_2,a_2\to a_3,\dots a_k\to a_1$,但是对于其他元素保持不变，即：$a\to a$,可将π记为
$$ \begin{array}{|c|c|c|c|c|}\hline a_1 & a_2 & a_3 & \dots & a_k \ \hline a_2 & a_3 & a_4 & \dots & a_1 \ \hline \end{array} $$
称为$k$阶循环，$K$为循环长度。每个置换都可以写成若干个互不相交的循环的乘积，且表示是唯一的.如
$$ \begin{array}{|c|c|c|c|c|c|} \hline 1 & 2 & 3 & 4 & 5 & 6 \ \hline 2 & 4 & 5 & 1 & 3 & 6 \ \hline \end{array} $$
则可以表示为$(124)(35)(6)$,置换的循环节数是上面的循环个数，上面的例题的循环节数为$3$.
定义：设$G$是有限集$X$上的置换群，点$a,b\in X$称为"等价"的，当且仅当，存在$\pi \in G$使得$\pi(a)=b$，记为$a~b$，这种等价条件下，$X$的元素形成的等价类称为$G$的轨道，它是集$X$的一个子集，$G$的任意两个不同的轨道之交是空集，所以置换群$G$的轨道全体是集合$X$的一个划分，构成若干个等价类，等价类的个数记为$L$。
$Z_k$ ($K$不动置换类)：设$G$是$1\dots n$的置换群。若$K$是$1\dots n$中某个元素，$G$中使$K$保持不变的置换的全体，记以$Z_k$，叫做$G$中使$K$保持不动的置换类，简称$K$不动置换类。
$E_k$(等价类)：设$G$是$1\dots n$的置换群。若$K$是$1\dots n$中某个元素，$K$在$G$作用下的轨迹，记作$E_k$。即$K$在$G$的作用下所能变化成的所有元素的集合。这个时候有：$|E_k|*|Z_k|=|G|$成立$(k=1,2,.....n)$。
$C(\pi)$：对于一个置换$\pi \in G$,及$a\in X$，若$\pi(a)=a$，则称$a$为$\pi$的不动点。$\pi$的不动点的全体记为$C(\pi)$。例如$\pi=(123)(3)(45)(6)(7), X={1,2,3,4,5,6,7}$;那么$C(\pi)={3,6,7}$共$3$个元素。
Burnside引理：
$$L = \frac{1}{|G|}(Z_1+Z_2+Z_3+Z_4+\dots+Z_k)$$ $$L = \frac{L1}{|G|}(C(\pi_1)+C(\pi_2)+C(\pi_3)+\dots+C(\pi_n))$$ (其中$k\in X,\pi \in G$)。
Polya定理：
设$G={\pi_1，\pi_2，\pi_3, \dots, \pi_n}$是$X={a_1，a_2，a_3, \dots, a_n}$上一个置换群，用$m$中颜色对$X$中的元素进行涂色，那么不同的涂色方案数为： $$\frac{1}{|G|}*(mC(\pi_1)+mC(\pi_2)+mC(\pi_3)+\dots+mC(\pi_k))$$其中$C(\pi_k)$为置换 $\pi_k$ 的循环节的个数。
polya定理求循环节个数
const int MAXN=1001;
int n, perm[MAXN], visit[MAXN]; //sum求循环节个数, Perm用来存储置换,即一个排列
int gcd(int n, int m) {
return m==0?n:gcd(m,n%m);
}
void Polya() {
int pos,sum=0;
memset(visit, 0x00, sizeof(visit));
for(int i=0; i<n; i++) {
if(!visit[i]) {
sum++; pos=i;
for(int j=0;!visit[perm[pos]];j++) {
pos=perm[pos];
visit[pos]=1;
}
}
}
return sum;
}
考虑旋转和翻转
1.旋转置换.
我们假设依次顺时针旋转$1~n$个,则循环个数为$gcd(i,n)$;
2.翻转置换
当$n$为偶数时,分两种情况,一种是中心轴在两个对称对象上,则循环个数为$n/2+1$,这样的置换有$n/2$个。另一种是对称轴两边分别有$n/2$个对象,则循环个数为$n/2$，这样的置换也有$n/2$个。
当$n$为奇数时,对称轴就只能在一个对象上,则循环个数为$n/2+1$;
例题：POJ 2409
题目链接：POJ 2409: http://poj.org/problem?id=2409
A bracelet is a ring-like sequence of s beads each of which can have one of c distinct colors. The ring is closed, i.e. has no beginning or end, and has no direction. Assume an unlimited supply of beads of each color. For different values of s and c, calculate the number of different bracelets that can be made.
理解：给定颜色种数和环上的珠子总数，问有多少种染色方案（通过旋转和翻转相同的算同一种）。可见，是简单的考虑旋转和翻转的Polya计数模型。题解：
#include <cstdio>
using namespace std;
inline long long gcd(long long a, long long b) {
return b==0?a:gcd(b, a%b);
}
long long llpow(long long a, long long b) {
return b==0?1:llpow(a, b-1)*a;
}
long long polya(long long n, long long m) {
long long sum = 0;
for(int i = 1; i <= m; ++i) {
sum += llpow(n, gcd(m, i));
}
if(m & 1) {
sum += m*llpow(n, (m>>1)+1);
}
else {
sum += (m>>1)*llpow(n, (m>>1)+1) + (m>>1)*llpow(n, m>>1);
}
return sum/2/m; // 去掉翻转和旋转的重复
}
int main(int argc, char **argv) {
long long n, m;
while(scanf("%lld%lld", &n, &m) != EOF && m+n > 0) {
printf("%lld\n", polya(n, m));
}
return 0;
}
例题：POJ 2154
题目链接：POJ 2154: http://poj.org/problem?id=2154
题目大意：将正n边形的n个顶点用n种颜色染色，问有多少种方案（答案mod p，且可由旋转互相得到的算一种）。
分析：顺时针旋转i格的置换中，循环的个数为$gcd(i,n)$，每个循环的长度为$n/gcd(i,n)$。如果枚举旋转的格数$i$，复杂度显然较高。因此，考虑不枚举$i$，反过来枚举$L$。由于$L|N$,枚举了$L$，再计算有多少个$i$使得$0<=i<=n-1$并且$L=gcd(i, n)$。即$gcd(i,n)=n/L$。
不妨设$a=n/L=gcd(i, n)$,设$i=a*t$则当且仅当$gcd(L,t)=1$时，有： $$Gcd(i,n)=gcd(a*L,a*t)=a$$ 因为$0<=i<n$,所以$0<=t<n/a=L$,所以满足这个条件的$t$的个数为$Euler(L)$.
欧拉函数：
$$\phi(x)=x(1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_3})\dots(1-\frac{1}{p_k})$$
其中$p_1, p_2, p_3, \dots, p_k$为$x$的所有质因数，$x$是不为$0$的整数。表示不超过$n$且与$n$互素的正整数的个数。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 36000;
int n, mod, ans, prim[35000];
bool flag[maxn + 20];
void get_prim() {
memset(flag, 0x00, sizeof (flag));
for(int i = 2; i <= 1000; i++) {
if(!flag[i]) {
for(int j = i * i; j <= maxn; j += i) {
flag[j] = true;
}
}
}
for(int i = 2, k = 0; i <= maxn; i++) {
if(!flag[i]) {
prim[k++] = i;
}
}
}
int eular(int n) { // phi function.
int i = 0, ans = 1;
for(i = 0; prim[i] * prim[i] <= n; i++) {
if(n % prim[i] != 0) {
continue;
}
ans *= prim[i] - 1; n /= prim[i];
while(n % prim[i] == 0) {
ans *= prim[i]; n /= prim[i];
}
}
if(n > 1) {
ans *= n - 1;
}
return ans % mod;
}
int pow_mod(int c, int k, int mod) {
int ans = 1;
c = c % mod;
while(k) {
if(k & 1) {
ans = (c * ans) % mod;
}
k >>= 1;
c = (c * c) % mod;
}
return ans;
}
int main() {
get_prim();
int i, T;
scanf("%d", &T);
while(T-- && scanf("%d%d", &n, &mod)) {
ans = 0;
for(i = 1; i * i <= n; i++) {
if (i * i == n) { //枚举循环长度l，找出相应的i的个数：gcd(i,n)=n/l.
ans = (ans + pow_mod(n, i - 1, mod) * eular(i)) % mod;
}
else if(n % i == 0) { //有长度为l的循环，就会有长度为n/l的循环。
ans = (ans + pow_mod(n, n / i - 1, mod) * eular(i) +
eular(n / i) * pow_mod(n, i - 1, mod)) % mod;
}
}
printf("%d\n", ans);
}
}
参考
Tags: Algorithm