公式：

Burnside引理： 1/|G|*(C(π1)+C(π2)+C(π3)+.....+C(πn))；

C(π)：指不同置换下的等价类数。例如π=(123)(3)(45)(6)(7)，X={1,2,3,4,5,6,7};那么C(π)={3,6,7}共3个等价类。

Polya定理： 1/|G|*(m^C(π1)+m^C(π2)+m^C(π3)+...+m^C(πk)).

设G={π1，π2，π3........πn}是X={a1，a2，a3.......an}上一个置换群，其中C(πk)为置换πk的循环节的个数。

eg:

POJ2409 Let it Bead

http://poj.org/problem?id=2409

题意：

有一个n长的项链，用m种颜色对其染色，有多少中不同的染色方法，项链可以旋转或者翻转。

思路：

用polya计数法，

对于旋转：每种旋转的循环节数就是gcd(i,n).

对于翻转：奇数时，按一个点与对边的轴翻转，循环节就是(n+1)/2,有n种。

偶数时，可以以两条对边翻转，循环节数就是n/2,可以以两对点翻转，循环节数就是(n+2)/2 ,分别有n/2种

代码：

long long n,m;

long long  flag,sum,ave,ans,res;

long long gcd(long long x,long long y)

{

    return y?gcd(y,x%y):x;

}

long long power(long long x,long long k)

{

    long long ans = 1;

    while(k)

    {

        if(k & 1) ans *= x;

        x *= x;

        k >>= 1;

    }

    return ans;

}

int main()

{

    int i,j,k,kk,t,x,y,z;

    while(scanf("%lld%lld",&m,&n)!=EOF&&n)

    {

        sum=0;

        for(i=1;i<=n;i++)

            sum+=power(m,gcd(n,i));

        if(n&1)sum+=(n*power(m,(n+1)/2));

        else sum+=(n/2*power(m,(n+2)/2)+n/2*power(m,n/2));

        sum/=(2*n);

        printf("%lld\n",sum);

    }

    return 0;

}

gym-101873B Buildings（polya计数）

ll qfast(ll x,ll y)

{

    ll ans=1;

    while(y)

    {

        if(y&1) ans=ans*x%mod;

        x=x*x%mod;

        y>>=1;

    }

    return ans%mod;

}

void run()

{

    ll n=rdll(),m=rdll(),c=rdll();

    ll x=qfast(c,n*n);

    ll ans=0;

    for(ll i=1;i<=m;i++)

    {

        ans+=qfast(x,__gcd(i,m));

        ans%=mod;

    }

    ans*=qfast(m,mod-2);

    printf("%lld\n",ans%mod);

}

signed main()

{

//  int t=rd();

//    while(t--)

    run();

    return 0;

}

巴特西

polay计数原理

eg:

POJ2409 Let it Bead

题意：

思路：

gym-101873B Buildings（polya计数）

最新文章

热门文章