polay计数原理

公式:polay计数原理

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|*(mC(π1)+mC(π2)+mC(π3)+...+mC(π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;
}

 

上一篇:2021-10-29


下一篇:Linux学习笔记