| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 7451 | Accepted: 3102 |
Description
Input
Output
Sample Input
4 5 -1
Sample Output
21 39
题解：给出红，绿，蓝3种颜色 的n个珠子，求能够组成多少个不同的项链。 （旋转 和 翻转后 相同的属于同一个项链）
看了好久大神的代码还是不太理解；暂时的理解是，对于每个循环节里的元素都有k中染色方案，所以是k^c(f);
现在只需要找出所有循环节的种数就好了；当然翻转和旋转循环节是不同的，翻转和旋转均有n种；所有种数加完要除以2n
Polya定理：
(1)设G是p个对象的一个置换群，用k种颜色给这p个对象，若一种染色方案在群G的作用下变为另一种方案，则这两个方案当作是同一种方案，这样的不同染色方案数为 
(2)对于N个珠子的项链，共有n种旋转置换和n种翻转置换。
对于旋转置换：每种置换的循环节数c(fi) = gcd(n,i)，(i为一次转过多少个珠子)
对于翻转置换：如果n为奇数，共有n种翻转置换，每种置换的循环节数均为c(f) = n/2 + 1; 如果n为偶数，分两种情况 <1> 从空白处穿对称轴，则轴两边各有n/2个对象，得到c(f) = n/2；
<2> 从两个对象上穿对称轴，则轴两边各有n/2-2个对象，得到c(f) = n/2 + 1。
代码：
#include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int INF=0x3f3f3f3f; #define mem(x,y) memset(x,y,sizeof(x)) #define SI(x) scanf("%d",&x) #define PI(x) printf("%d",x) typedef long long LL; int gcd(int a,int b){return b==0?a:gcd(b,a%b);} int main(){ int n; while(~SI(n),n!=-1){ LL ans=0; if(!n){ puts("0");continue; } for(int i=1;i<=n;i++) ans+=pow(3,gcd(i,n)); ans+=n*(n&1?pow(3,n/2+1):(pow(3,n/2)/2+pow(3,n/2+1)/2)); printf("%lld\n",ans/(2*n)); } return 0; }
原文：http://www.cnblogs.com/handsomecui/p/5233812.html