Chlience

【算法】Ploya定理
在上一篇文章 Burnside 引理 中我们讲到,可以用计算 $D(a_i)$ 的方式来找出要多少个本质不同的元素...
扫描右侧二维码阅读全文
12
2019/01

【算法】Ploya定理

在上一篇文章 Burnside 引理 中我们讲到,可以用计算 $D(a_i)$ 的方式来找出要多少个本质不同的元素数

但是,朴素的去找 $D(a_i)$ 是很慢的,需要枚举每一种置换,每一种排列(元素),以及检查每个位置是否相同,时间复杂度 $O(nsp)$,分别代表元素个数,置换个数,所有的格子数

而 $Polya$ 定理就很妙了,可以将其降为 $O(sp)$,具体如何实现呢?

引入一个循环的概念:

$$ (a_1a_2\cdots a_n)= \begin{pmatrix} a_1 & a_2 & \cdots & a_{n-1} & a_n\\ a_2 & a_3 & \cdots & a_n & a_1 \end{pmatrix} $$

称为 $n$ 阶循环

同时,每个置换都可以写为若干个互不相交的循环的乘积,两个循环不相交是指对于 $(a_1a_2\cdots a_n),(b_1b_2\cdots b_m)$,$\forall a_i\neq b_j$
$eg:$

$$ \begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 3 & 5 & 1 & 4 & 2 \end{pmatrix} = (13)(25)(4) $$

如果不考虑先后顺序的话,这样的表示是唯一的,置换的循环节数就是上列表示中循环的个数,在上面的例子中,循环节数为 $3$

正式介绍 $Ploya$ 定理:设 $G$ 是 $p$ 个对象的一个置换群,用 $m$ 种颜色涂染 $p$ 个对象,则不同方案为:

$$ L=\frac{1}{|G|}\sum_{i=1}^sm^{c(g_i)} $$

要在置换下得到稳定不动的方案,那么只能将每个循环节染上相同的颜色,所以$D(g_i)=m^{c(g_i)}$

还是之前的那个例子:

$$ G=\{\text{旋转0°,旋转90°,旋转180°,旋转270°}\}\\ g_1=\begin{pmatrix} 1 & 2 & 3 & 4\\ 1 & 2 & 3 & 4 \end{pmatrix} =(1)(2)(3)(4)\\ g_2=\begin{pmatrix} 1 & 2 & 3 & 4\\ 4 & 1 & 2 & 3 \end{pmatrix} =(1234)\\ g_3=\begin{pmatrix} 1 & 2 & 3 & 4\\ 3 & 4 & 1 & 2 \end{pmatrix} =(13)(24)\\ g_4=\begin{pmatrix} 1 & 2 & 3 & 4\\ 2 & 3 & 4 & 1 \end{pmatrix} =(1234) $$

$$ m^{c(g_1)}=2^4=16\\ m^{c(g_2)}=2^1=2\\ m^{c(g_3)}=2^2=4\\ m^{c(g_4)}=2^1=2\\ L=\frac{1}{|G|}(m^{c(g_1)}+m^{c(g_2)}+m^{c(g_3)}+m^{c(g_4)})=\frac{1}{4}(16+2+4+2)=6 $$

为什么在 $Burnside$ 引理中每个置换有 $16$ 个元素而在这里只有 $4$ 个元素呢?
$Burnside$ 引理中需要考虑每个点的颜色及其相对位置,而知在 $Polya$ 定理中,只需要考虑四个元素间的相互转换
一个是排列之间的置换,一个是点的置换,这里必须要分清楚

同样,对于每一个置换 $g_i$ ,当且仅当将每个循环染成相同的颜色时,它在置换中属于不动点,一共有 $m^{c(g_i)}$ 个不动点,所以 $D(g_i)=m^{c(g_i)}$,即 $L=\frac{1}{|G|}\sum_{i=1}^sD(a_i)=\frac{1}{|G|}\sum_{i=1}^sm^{c(g_i)}$

证毕

接下来给出一个例题,通过这个来了解 $Polya$ 在 $OI$ 中最简单的应用:
POJ 2409

求 $n$ 种颜色,长度为 $m$ 的环有多少种本质不同的染色方案?

考虑旋转和翻转两种情况

旋转置换共有 $m$ 种,分别旋转 $[\frac{1}{m}2\pi,\frac{m}{m}2\pi]$ 度
旋转 $\frac{i}{m}2\pi$ 度,或者说旋转 $i$ 位时,循环节数显然是 $gcd(i,m)$,考虑转多少次能转回原点就好了

翻转置换共有两种情况
当 $m$ 为偶数,可以以相对的两个点为对称轴,所以其他的每对点组成一个循环节,在对称轴上的两个点为两个循环节,所以总节数为 $\frac{m-2}{2}+2$,共有 $\frac{m}{2}$ 种置换
当然,你也可以用两条相对的边作为对称轴,所以每对点组成一个循环节,总节数为 $\frac{m}{2}$,共有 $\frac{m}{2}$ 种置换

当 $m$ 为奇数。那么只能是一个点和其相对的边作为对称轴,其他的每对点组成一个循环节,总节数为 $\frac{m-1}{2}+1$,共有 $m$ 种置换

然后将所有贡献加起来除去置换的总数即可

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
ll m , n , ans;
ll read() {
    ll ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a;}
ll qpow(ll a , ll b) {
    ll ans = 1;
    while(b) {
        if(b & 1) ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}
int main() {
    while(1) {
        m = read(); n = read(); 
        if(!n && !m) return 0;
        ans = 0;
        for(ll i = 1 ; i <= n ; ++ i)
            ans += qpow(m , gcd(i , n));
        if(n % 2) {
            ans += qpow(m , (n - 1) / 2 + 1) * n;
            ans /= 2 * n;
        }
        else {
            ans += qpow(m , n / 2) * (n / 2);
            ans += qpow(m , (n - 2) / 2 + 2) * (n / 2);
            ans /= 2 * n;
        }
        printf("%lld\n" , ans);
    }
}
Last modification:January 13th, 2019 at 02:56 pm

Leave a Comment