POJ 1286-Necklace of Beads（Polya定理-旋转+翻转串项链）

梦里梦外; 2022-06-17 05:53 144阅读 0赞

Necklace of Beads

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;10000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;8298</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;3467</td> 
  </tr> 
 </tbody> 
</table>

Description

Beads of red, blue or green colors are connected together into a circular necklace of n beads ( n < 24 ). If the repetitions that are produced by rotation around the center of the circular necklace or reflection to the axis of symmetry are all neglected, how many different forms of the necklace are there?  
![1286_1.jpg][]

Input

The input has several lines, and each line contains the input data n.  
\-1 denotes the end of the input file.

Output

The output should contain the output data: Number of different forms, in each line correspondent to the input data.

Sample Input

4
    5
    -1

Sample Output

21
    39

Source

[Xi'an 2002][Xi_an 2002]

和[POJ 2409][] 几乎一毛一样(๑°ㅁ°๑)‼

## 题目意思： ##

给定3种颜色的珠子，每种颜色的珠子个数不限，将它们串成长度为n的项链，计算一共能做成多少种不重复的项链。

两条项链相同，当且仅当两条项链能通过旋转或者翻转后能重合在一起。

## 解题思路： ##

①旋转，将项链顺时针旋转i格之后，其循环节数是gcd(n,i)，计算出所有不同的着色方案；

②翻转，不同的方法数=循环群个数\*pow（不同颜色数,循环节数）之和，然后再除以所有的置换数之和（2\*n），其中：

当n为奇数，共有n个循环节数为(n+1)/2的循环群；

当n为偶数，共有n/2个循环节数为(n+2)/2的循环群和n/2个循环节数为n/2的循环群。

注意用long long，注意特判0.

#include<cstdio>
    #include<cmath>
    #include<vector>
    #include<algorithm>
    using namespace std;
    long long gcd(long long a,long long b)
    {
        return (a%b!=0?(gcd(b,a%b)):b);
    }
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("G:/cbx/read.txt","r",stdin);
        //freopen("G:/cbx/out.txt","w",stdout);
    #endif
        int n;
        while(~scanf("%d",&n))
        {
            if(n==-1) break;
            long long ans=0;//注意数据很大要用long long
            if(n==0)//注意特判，不然RE
            {
                printf("0\n");
                continue;
            }
            for(int i=1; i<=n; ++i) //旋转
            {
                long long t=gcd(n,i);
                ans+=(long long)(pow(3,t));
            }
            //翻转
            if(n&1)//奇数
                ans+=(long long)(n*pow(3,(n+1)/2));
            else
            {
                ans+=(long long)(n/2*pow(3,(n+2)/2));
                ans+=(long long)(n/2*pow(3,(n)/2));
            }
            ans/=2*n;
            printf("%I64d\n",ans);
        }
        return 0;
    }

[1286_1.jpg]: /images/20220617/db6228a2ba9a462f84c49d9751b384d8.png
[Xi_an 2002]: http://poj.org/searchproblem?field=source&key=Xi%27an+2002
[POJ 2409]: http://blog.csdn.net/mikasa3/article/details/70231412