Polya定理是个很神奇的东西~
题目大意：
n个珠子串成一个圆，用三种颜色去涂色。问一共有多少种不同的涂色方法。
不同的涂色方法被定义为：如果这种涂色情况翻转，旋转不与其他情况相同就为不同。
解题思路：
Polya定理模版题。
对于顺时针长度为i的旋转，为pow(3,__gcd(n,i)；
对于翻转，当为奇数时，有：n*pow(3.0,n/2+1);
当为偶数时，有：n/2*pow(3.0,n/2)+n/2*pow(3.0,n/2+1);
一共有2*n种情况，最后要除以2*n
下面是代码：
#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #define clear(A, X, SIZE) memset(A, X, sizeof(A[0]) * (SIZE)) #define clearall(A, X) memset(A, X, sizeof(A)) #define memcopy1(A , X, SIZE) memcpy(A , X ,sizeof(X[0])*(SIZE)) #define memcopy1all(A, X) memcpy(A , X ,sizeof(X)) #define max( x, y ) ( ((x) > (y)) ? (x) : (y) ) #define min( x, y ) ( ((x) < (y)) ? (x) : (y) ) using namespace std; int main() { int n; while(scanf("%d",&n),n!=-1) { if(n<=0) //注意n没有最小值范围哦 { puts("0"); continue; } long long ans=0; for(int i=1; i<=n; i++)ans+=pow(3,__gcd(n,i)); //旋转置换情况 //翻转置换情况 if(n&1)ans+=n*pow(3.0,n/2+1); //当为奇数个时 else //当为偶数个时 { ans+=n/2*pow(3.0,n/2); ans+=n/2*pow(3.0,n/2+1); } ans/=2*n; //polya计数公式，共有2*n种情况 cout<<ans<<endl; } return 0; }
转载于:https://www.cnblogs.com/lin375691011/p/3996635.html
