大致题意：给你三种颜色的珠子，和一个长度为N(N<24)的项链，用这三种珠子串成这个项链，项链可以旋转和翻转，经过旋转和翻转所得的项链视为同一种项链，现在告诉你项链的长度s，求共能组成几条不同的项链。
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 20000/10000K (Java/Other)
样例:
看到这个题的题意，肯定是计数法没跑啦，而且是那种最水的，颜色固定就3种，而且项链的长度也很小，而且也没有条件限制，模版稍稍一套就能过，连优化算法都不用上，稍稍被坑在s=0的情况上了。
思路：用polya 定理解决这个计数问题，关键是分析群中置换的个数和每个置换的循环节个数，分析题目中的两种置换群，一种是旋转置换，一种是翻转置换，这两种变换都是刚性变换。
对于旋转置换群，群内置换的总个数显而易见是n个（转n次就返回到自己了嘛），第i个置换中循环节的个数可以用dfs搜索出来，不过有直接的结论，循环节个数应该是gcd(n,i)个，这个结论所有博客都给出了，但是几乎都没给证明（大神都觉得太显而易见了吧）。
在此我给出证明：在任意一个旋转中，不妨设旋转的角度为i（0=<i<n）弧度，任意选取一个点x，那么从x开始以i弧度为单位进行旋转，那么它将经过LCM(i,n)/i次旋转回到x自己。想不清楚可以举个例子看看，就拿上面图的n=4，i=2为例，那个green的球经过两次弧度为i=2的旋转就回到了自己。明白了这个问题就迎刃而解了，由于选取的点是任意的，所以所有点所在的循环节的长度就是LCM(i,n)/i，这也就说明在旋转置换中所有节的长度都相等，n/(LCM(i,n)/i)应该就是循环节的个数了，n/(LCM(i,n)/i)=gcd(n,i)这很明显，所以给出的结论成立。注意：此结论得出的循环节个数只适用于二维旋转置换，别乱用啊。
对于翻转置换，看上面的那个图，它已经给了你很大提示，找循环节的关键是找对称轴。这里n要分奇偶性。
当n为奇数，那么对称轴就是每个点和圆心的连线，共n条（观察第二个图），那么显然除了这个点没变，其他的点都跟对称的那个点置换了，所以循环节的个数是（n-1）/2+1。
当n为偶数，那么对称轴有每个点和对面的点的连线，共n/2条，显然除了对称轴上的两个点，其余点都跟对面的点置换了循环节的个数是(n-2)/2+2，两个相邻点中点和圆心的连线也是n/2条，显然每个点都跟对面的点置换了，循环节的个数是n/2，n为偶也是n条对称轴，（观察第一个图）。
分析至此，求这个题就没难度了，由于我采取了最笨的枚举i法，所以时间复杂度O(sp)，s为置换个数，p为项链珠子数，但是A此题还是妥妥的。
多说几句，polya定理是在burnside引理的基础上得出的结论，能快速求一个置换下不变元素（稳定核）的个数，但它不是万能的，如果条件多的计数，还是burnside好使。
个人非常喜欢做计数法的题，感觉出的题目都很有意思，而且计数法的题难度还是比较大的，限制条件多了就很难搞，以后有时间会针对用burnside定理和polya定理解决计数问题作总结。
1 #include<cstdio> 2 #include<cmath> 3 using namespace std; 4 typedef __int64 ll; 5 int gcd(int a,int b){ 6 if(b==0){ 7 return a; 8 } 9 return gcd(b,a%b); 10 } 11 int c=3,s; 12 ll polya(){ 13 int i,j; 14 ll ans=0; 15 for(i=0;i<s;i++){ 16 ans+=(ll)pow(1.0*c,gcd(s,i)); 17 } 18 if(s%2){ 19 ans+=s*(ll)pow(1.0*c,s/2+1); 20 } 21 else{ 22 ans+=s/2*(ll)pow(1.0*c,s/2); 23 ans+=s/2*(ll)pow(1.0*c,s/2+1); 24 } 25 return ans/2/s; 26 } 27 int main(){ 28 ll ans; 29 while(scanf("%d",&s)){ 30 if(s==-1)break; 31 if(s==0)ans=0; 32 else ans=polya(); 33 printf("%I64d\n",ans); 34 } 35 return 0; 36 }