Polya定理入门学习&POJ1286

2017-09-25

Polya定理应用简单介绍

polya定理主要是用于解决等价类计数问题的，所谓等价类计数问题是指题目中会定义一种等价关系，满足这个关系的元素都会被看成同一类，并只需要统计一次，最终需要统计所有的不同方案数。

最经典的就是手链问题，手链是个圆形的由n个珠子串成的，用m种颜色染上面的每一颗珠子，能得到多少种方法，如果旋转或者翻转得到的同样的类型就视为同一种方法。

解决方法

将可以视作等价类的条件看作是一种置换群，比如珠子数量n=4，如果是顺时针旋转90度，那么得到的置换群就是

0 1 2 3

1 2 3 0

这样将所有的置换群列举出来。可以列举的置换群总数是|G|，每一类置换群得到的结果都是这个置换群中循环的个数$c(g_i)$，保证循环中染色都是一样的，这样才能保证置换后等价。如果可以染的颜色数量没有限制，那么答案很简单就是
$$
f(n, m ) = \frac{1}{|G|} \sum_{i=1}^{|G|}m^{c(g_i)}
$$
对于旋转来说，旋转了k个位置，$c(g_k) = gcd(n,k)$

对于对称来说，在这个例子中区分奇偶性即可

那么根据这个gcd就很容易计算对应的数量了。

有时候为了优化代码，会考虑计算得到对应gcd的值d，一共有多少种可能性，这个只要考虑$\phi(n/d) \quad s.t. \space d|n$。这个函数$\phi(x)$表示和x互质的小于等于x的数字的个数，这个函数利用积性函数的性质在O(n)的线性时间内初始化算出来。

POJ1286

问题

圆环上n个珠子，用3种颜色染色，旋转或者翻转后保持一致的视为同一种方法，求得到的方法数

//简单使用gcd的方法
#include <iostream>
#include <cstdio>
using namespace std;
#define LL long long
#define pli pair<LL,int>
LL mi[30];
void init_mi()
{
    mi[0] = 1;
    for(int i=1 ; i<30 ; i++)
        mi[i] = mi[i-1]*3;
}
int gcd(int x, int y){return y==0?x:gcd(y,x%y);}
pli rotate(int n)
{
    LL ret = 0;
    for(int i=1 ; i<=n ; i++){
        ret += mi[gcd(n,i)];
    }
    return make_pair(ret,n);
}
pli symmetry(int n)
{
    LL ret = 0;
    if(n&1){
        ret += mi[n/2+1]*n;
        return make_pair(ret, n);
    }
    else{
        ret += mi[n/2]*n/2; //对称轴不在点上
        ret += mi[n/2+1]*n/2; //对称轴在点上
        return make_pair(ret, n);
    }
}
int main()
{
    //freopen("in.txt" , "r" , stdin);
    int n;
    init_mi();
    while(~scanf("%d" , &n) && n!=-1){
        if(n<=0) {cout<<0<<endl;continue;}
        pli v1 = rotate(n);
        pli v2 = symmetry(n); œ
        cout<<(v1.first+v2.first)/(v1.second+v2.second)<<endl;
    }
    return 0;
}

//利用phi函数优化的算法
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
#define LL long long
#define pli pair<LL,int>
namespace prime{
    #define N 10000
    int pri[N+5] , tot , phi[N+5];
    bool vis[N+5];
    void init_phi(){
        memset(vis , 0 , sizeof(vis));
        phi[0] = 0 , phi[1] = 1;
        for(int i=2 ; i<=N ; i++){
            if(!vis[i]){
                pri[tot++] = i;
                phi[i] = i-1;
            }
            for(int j=0 ; j<tot ; j++){
                if(pri[j]*i > N) break;
                vis[pri[j]*i] = true;
                if(i%pri[j] == 0){phi[pri[j]*i] = pri[j]*phi[i] ; break;}
                else phi[pri[j]*i] = phi[i]*phi[pri[j]];
            }
        }
    }
}
using namespace prime;
LL mi[30];
void init_mi()
{
    mi[0] = 1;
    for(int i=1 ; i<30 ; i++)
        mi[i] = mi[i-1]*3;
}
int gcd(int x, int y){return y==0?x:gcd(y,x%y);}
pli rotate(int n)
{
    LL ret = 0;
    int tmp = sqrt(n+0.5);
    
    for(int d=1 ; d<=tmp ; d++){
        if(n%d == 0){
            ret += phi[n/d]*mi[d];
            if(n/d!=d) ret += phi[d]*mi[n/d];
        }
    }
    return make_pair(ret,n);
}
pli symmetry(int n)
{
    LL ret = 0;
    if(n&1){
        ret += mi[n/2+1]*n;
        return make_pair(ret, n);
    }
    else{
        ret += mi[n/2]*n/2; //对称轴不在点上
        ret += mi[n/2+1]*n/2; //对称轴在点上
        return make_pair(ret, n);
    }
}
int main()
{
   // freopen("in.txt" , "r" , stdin);
    int n;
    init_phi();
    init_mi();
    while(~scanf("%d" , &n) && n!=-1){
        if(n<=0) {cout<<0<<endl;continue;}
        pli v1 = rotate(n);
        pli v2 = symmetry(n);
        cout<<(v1.first+v2.first)/(v1.second+v2.second)<<endl;
    }
    return 0;
}

其他类似的题目还有，HDOJ：2084、2647、1812、3411、2865、2481。POJ：1286、2409、2154、2888。