polya定理小结

polya的精髓就在与对循环节的寻找，其中常遇到的问题就是项链染色类问题。

当项链旋转时有n种置换，循环节的个数分别是gcd(n, i);

当项链翻转时有n种置换,其中当项链珠子数位奇数时，循环节的个数是n/2+1

当项链珠子数是偶数个时,当翻转线穿过珠子时，循环节个数为n/2+1,否则为n/2;

1.poj 1286:

题目大意：用三种颜色对珠子数不超过24的项链染色，问有多少种染色情况。

这道题是最基本的polya定理考察，只要带入公式即可

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

const long long maxa = ;

long long edge[maxa];

void rotate(long long n, long long ii){

    for(long long i = ; i < n; i++){

        edge[(i+ii)%n] = i;

    }

}

void turn(long long n, long long ii){

    for(long long i = n-, j= ; i >= ; i--, j++){

        edge[(j+ ii)%n] = i;

    }

}

long long vis[maxa];

void dfs(long long i){

    if(vis[i] == )return ;

    vis[i] = ;

    dfs(edge[i]);

}

int main(){

    int n, m;

    while(scanf("%d%d", &m, &n), n+m){

        if(n == ){

            printf("0\n");

            continue;

        }

        long long ans = ;

        for(long long i = ; i < n; i++){

            rotate(n, i);

            long long o = ;

            memset(vis, , sizeof(vis));

            for(long long k = ;k  < n; k++){

                if(vis[k]==){

                    o ++;

                    dfs(k);

                }

            }

            long long sum = ;

            for(long long k = ;k  < o; k++){

                sum *= m;

            }

            ans += sum;

        }

        for(long long i = ; i < n; i++){

            turn(n, i);

            long long o = ;

            memset(vis, , sizeof(vis));

            for(long long k = ;k  < n; k++){

                if(vis[k]==){

                    o ++;

                    dfs(k);

                }

            }

            long long sum = ;

            for(long long k = ;k  < o; k++){

                sum *= m;

            }

            ans += sum;

        }

        cout<<ans/n/<<endl;

    }

}

2.poj 2409

题目大意，用c种颜色染n个珠子组成的项链，也是最基本的polya定理考察

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

const long long maxa = ;

long long edge[maxa];

void rotate(long long n, long long ii){

    for(long long i = ; i < n; i++){

        edge[(i+ii)%n] = i;

    }

}

void turn(long long n, long long ii){

    for(long long i = n-, j= ; i >= ; i--, j++){

        edge[(j+ ii)%n] = i;

    }

}

long long vis[maxa];

void dfs(long long i){

    if(vis[i] == )return ;

    vis[i] = ;

    dfs(edge[i]);

}

int main(){

    int n, m;

    while(scanf("%d%d", &m, &n), n+m){

        if(n == ){

            printf("0\n");

            continue;

        }

        long long ans = ;

        for(long long i = ; i < n; i++){

            rotate(n, i);

            long long o = ;

            memset(vis, , sizeof(vis));

            for(long long k = ;k  < n; k++){

                if(vis[k]==){

                    o ++;

                    dfs(k);

                }

            }

            long long sum = ;

            for(long long k = ;k  < o; k++){

                sum *= m;

            }

            ans += sum;

        }

        for(long long i = ; i < n; i++){

            turn(n, i);

            long long o = ;

            memset(vis, , sizeof(vis));

            for(long long k = ;k  < n; k++){

                if(vis[k]==){

                    o ++;

                    dfs(k);

                }

            }

            long long sum = ;

            for(long long k = ;k  < o; k++){

                sum *= m;

            }

            ans += sum;

        }

        cout<<ans/n/<<endl;

    }

}

3.hdu 1812

题目大意，用c种颜色对n*n的棋盘染色，有多少种方法

其实这道题就是可以看成一些(n+1)/2串项链，有八种置换，但是最坑的是大数怎么写都超时....万进制优化也超时.....打表还不让大那么大，java是很好的解决方法...谁爱写谁写....反正我不写啦啦啦啦

4.poj 2154

题目大意，用n种颜色染长度是n的项链，结果mod p n<=10^9,p<= 30000,这里的项链只考虑旋转。

常规解法是这样sum（n^gcd（n,i)）%q,但是数据太大了不允许，我们知道的是n的因子数是可以通过搜索求出来的，那么如果gcd(n,i) == m，则i的数量显然是euler(i)，需要注意的是最后除n的时候，n和p不一定互质所以需要在之前做处理，也就是将公式变成了sum（n^gcd（n,i)-1）%q，需要注意的是开long long会超时，所以在要用int，有些部分需要用同余模定理优化。

#include<iostream>

#include<string.h>

#include<cmath>

#include<stdio.h>

using namespace std;

const int maxa = ;

int app[maxa][];

int o;

int ans;

int n, q;

int m;

int euler(int n){ //返回euler(n)

     //if(n == 1)return 0;

     int res=n,a=n;

     for(int i=;i*i<=a;i++){

         if(a%i==){

             res=res/i*(i-);//先进行除法是为了防止中间数据的溢出

             while(a%i==) a/=i;

         }

     }

     if(a>) res=res/a*(a-);

     return res;

}

int kuick(int a, int b){

    int aa = ;

    if(b == )return ;

    aa = kuick(a, b/);

    aa *= aa;

    aa%= q;

    if(b &) aa*= a;

    aa %= q;

    return aa;

}

void dfs(int ii, int nn){//cout<<"*"<<ii<<" "<<o<<" "<<nn<<endl;

    if(ii == o){

        int aa = euler(n/nn) % q;

        ans += aa * kuick(n%q, nn-);

        ans %= q;

        return;

    }

    dfs(ii+, nn);

    int ss = ;

    for(int i = ; i < app[ii][]; i++){

        ss *= app[ii][];

        dfs(ii+, ss*nn);

    }

}

int main(){

    cin>>m;

    while(m--){

        cin>>n>>q;

        int N = n;

        ans = ;

        int sq = sqrt(n);

        o = ;

        for(int i = ;i  <= sq; i++){

            if(n % i == ){

                app[o][] = i;

                app[o][] = ;

                while(n %i ==){

                    app[o][]++;

                    n /= i;

                }

                o++;

            }

        }

        //printf("*");

        if(n != ){

            app[o][] = n;

            app[o++][] = ;

        }

        n = N;

        dfs(, );

        cout<<ans<<endl;

    }

}

巴特西

polya定理小结

最新文章

热门文章