POJ 1286 Necklace of Beads （Polya定理）

Myth丶恋晨 2022-06-15 04:22 141阅读 0赞

题目链接：  
[POJ 1286][]

题意：就是求这样的三种颜色的组合有多少种？旋转和对称的重复的不算。  
![这里写图片描述][1286_1.jpg]

题解：Polya定理题。主要考虑旋转和对称的情况。

#### 旋转： ####

当n=4时，可顺时针旋转0、1、2、3格  
0格：（1）（2）（3）（4）可以互相转化  
1格：（1,2,3,4）可以互相转化  
2格：（1,3）（2,4）可以互相转化  
3格：（1,2,3,4）可以互相转化  
所以，ans=(34\+31\+32\+31)4=24

#### **旋转：顺时针旋转i格的置换中，循环的个数为gcd（i，n），每个循环的长度为n/gcd(i,n)** ####

同理，当n=5时，ans=(35\+31\+31\+31\+31)5=51。

#### 对称： ####

当n=4时，有4条对称轴  
其中2条，（1,2）（3,4）可以互相转化  
另外2条，（1）（3）（2,4）可以互相转化  
ans=(2∗32\+2∗33)4=18  
当n=5时，有5条对称轴  
每一条，（1）（2,5）（3,4）  
ans=(5∗33)5=27  
以此类推。  
最终ans=（旋转\+对称）2。  
所以就可以写代码了。

代码：

//#include <bits/stdc++.h>
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    typedef long long ll;
    ll q_pow(ll a,ll b)
    {
        ll ans =1;
        while(b)
        {
            if(b&1){
                ans=(ans*a);
            }
            b>>=1;
            a=a*a;
        }
        return ans;
    }
    ll n;
    ll gcd(ll a,ll b)
    {
        return b==0?a:gcd(b,a%b);
    }
    int main()
    {
        while(~scanf("%lld",&n))
        {
            if(n==-1)break;
            if(n==0){
                puts("0");continue;
            }
            ll ans = 0;
            if(n&1)
            {
                ans += q_pow(3,n/2+1)*n;
            }
            else
            {
                ans +=q_pow(3,n/2+1)*(n/2) + q_pow(3,n/2)*(n/2);
            }
            for(int i=1;i<=n;i++)
            {
                ans +=q_pow(3,gcd(i,n));
            }
            cout<<ans/(2*n)<<endl;
        }
        return 0;
    }

[POJ 1286]: http://poj.org/problem?id=1286
[1286_1.jpg]: /images/20220615/dab8629f25cd46478f0c9eb3d7c626e6.png