参考资料：
感觉近期一直easy遇见这样的题目....... 略微复杂一点的就不太会
先是一个总结出来的定理：
用一个最简单的样例来说明
对2*2的方阵用黑白两种颜色涂色，问能得到多少种不同的图像？经过旋转使之吻合的两种方案，算是同一种方案。
设G={p1,p2,…,pg}是Ω上的一个置换群比方置换群G={转0°。转90°，转180°，转270°}
C(pk)是置换pk的循环的个数
G1置换{转0° }的循环节是4。 {(1),(2),(3),(4)}
G2置换{转90° }的循环节是1， {(4,3,2,1)}
G3置换{转180°}的循环节是2， {(1,3),(2,4)}
G4置换{转270°}的循环节是1。 {(1,2,3,4)}
用M中的颜色对Ω中的元素着色，
着色方案数为 L = 1/|G|*[c1(p1)+c1(p2)+c1(p3)+...c1(p[g])]
= 1/|G|*[m^c(p1)+m^c(p2)+m^c(p3)+...m^c(p[g])]
|G|为置换的总个数,m颜色数
c1(pi)指置换pi的不动点的数目（既循环节为1的点数）
明显四个数分别为 16 2 4 2
L = 1/|G| * [16 + 2 + 4 + 2] = 6
c(pi)指的是置换pi的循环个数。
L = 1/|G| *[ 2^4 + 2^1 + 2^2 + 2^1 ] = 6
先来一个简单的题目：
poj 2409 :
id=2409
题目大意：
一家项链公司生产手镯。n颗珠子形成一个环，用m种颜色给n颗珠子染色，就得到了各种各样的手镯。可是，经过旋转和翻转使之吻合的算同一种方案。
比如，当用2种颜色对5颗珠子进行染色的方案数为8。
题目解法：
一： 旋转 （比方说是有n个珠子。每次能够旋转的角度就是360/n）
二： 翻转 （考虑对称轴。奇数个珠子，那每次对称轴能够穿过一个珠子。则一共同拥有n个对称轴）
偶数个珠子，每一个对称轴穿过的是两个珠子，一共同拥有n/2个对称轴，或者说每一个对称轴不穿过珠子，这种对称轴也是n/2个
所以综上来说无论是奇数或者偶数。其变化方式都是有2*n种翻转。
能够证明的是每个翻转其循环节各自是gcd(i,n) 0<i<=n
#include#include #include #include using namespace std;int gcd(int a,int b){ return b==0?a:gcd(b,a%b);}long long rotate(int c,int n){ //旋转 旋转 (360/n) * i 度 long long sum=0; for(int i=1;i<=n;i++) sum+=pow(c*1.0,gcd(n,i)); //每次旋转的循环节是gcd(n,i) return sum;}long long turn(int c,int n){ //翻转 long long sum=0; if(n%2) sum+=n*pow(c*1.0,(n+2)/2); //奇数则对称轴都是穿过一个珠子 一共n个 每一个置换的循环节是n/2+1 else sum+=n/2*(pow(c*1.0,n/2)+pow(c*1.0,(n+2)/2)); //偶数则穿过珠子或者不穿过珠子 各自是n/2 个 循环节是n/2+1 和 n/2 能够用下面公式算出 return sum;}void polya(int c,int n){ int i,j; long long sum=0; sum+=rotate(c,n); sum+=turn(c,n); printf("%lld\n",sum/(2*n));}int main(){ int n,m; while(scanf("%d%d",&n,&m),n||m){ polya(n,m); } return 0;}
#include#include #include #include #include #include #include #include #include #include
版权声明：本文博客原创文章。博客，未经同意，不得转载。