poj1286Necklace of Beads(ploya定理）

链接

这个东东是新知识 let's 从头学起吧

这篇文库讲的不错至少把各种概念学了一遍

然后再看此题共有两种类型的置换一种是旋转之后相同算一种一种是翻转之后相同算一种

对于旋转共有N次置换转1下到转N下对于每一次的循环节各大牛给出了结论为gcd(n,i) 这个我也不会证姑且记住吧

对于翻转这个从图中可以看出来找对称轴分2种情况

if n%2==0 也分两种情况若以两个相对的珠子为对称轴那循环节为（n-2)/2+2 若以其它不含珠子的线为对称轴循环节为n/2 个置换n/2次

else (n-1)/2+1

然后就可以按ploya定理做了文库有讲就不说ploya是什么了

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<cmath>
 7 using namespace std;
 8 int n;
 9 #define LL long long
10 int gcd(int a,int b)
11 {
12     return b==0?a:gcd(b,a%b);
13 }
14 int main()
15 {
16     int i;
17     while(scanf("%d",&n)!=EOF)
18     {
19         if(n==-1) break;
20         LL ans=0;
21         if(n==0)
22         {
23           printf("0
");
24           continue;  
25         }
26         for(i = 1; i <= n ; i++)
27         ans +=(LL)pow(3.0,gcd(n,i));
28         if(n%2)
29         ans+=n*(LL)pow(3.0,(n-1)/2+1);
30         else
31         {
32             ans+=n/2*(LL)pow(3.0,(n-2)/2+2);
33             ans+=n/2*(LL)pow(3.0,n/2);
34         }
35         printf("%lld
",ans/2/n);
36     }
37     return 0;
38 }

View Code