首页 > 代码库 > polay定理总结
polay定理总结
参考资料:polay定理
感觉最近一直容易遇见这种题目....... 稍微复杂一点的就不太会
先是一个总结出来的定理:
用一个最简单的例子来说明
对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 : http://poj.org/problem?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 <iostream> #include <stdio.h> #include <string.h> #include <math.h> 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<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define eps 1e-7 #define INF 0x7FFFFFFF #define LLINF 0x7FFFFFFFFFFFFFFF #define seed 1313131 #define MOD 1000000007 #define ll long long #define ull unsigned ll #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 //求置换的循环节,polya原理 //perm[0..n-1]为0..n-1的一个置换(排列) //返回置换最小周期,num返回循环节个数 #define MAXN 1000 int gcd(int a,int b){ return b?gcd(b,a%b):a; } int polya(int* perm,int n,int& num){ int i,j,p,v[MAXN]={0},ret=1; for (num=i=0;i<n;i++) if (!v[i]){ for (num++,j=0,p=i;!v[p=perm[p]];j++) v[p]=1; ret*=j/gcd(ret,j); } return ret; } int main (){ int perm1[6]={0,5,4,3,2,1}; int perm2[6]={1,0,5,4,3,2}; int num; cout<<polya(perm2,6,num)<<endl; cout<<num<<endl; }
polay定理总结