首页 > 代码库 > [ACM] POJ 2409 Let it Bead (Polya计数)
[ACM] POJ 2409 Let it Bead (Polya计数)
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 4434 | Accepted: 2916 |
Description
A bracelet is a ring-like sequence of s beads each of which can have one of c distinct colors. The ring is closed, i.e. has no beginning or end, and has no direction. Assume an unlimited supply of beads of each color. For different values of s and c, calculate the number of different bracelets that can be made.
Input
Output
Sample Input
1 1 2 1 2 2 5 1 2 5 2 6 6 2 0 0
Sample Output
1 2 3 5 8 13 21
Source
第一道Polya计数题,感觉还是不太懂。。群那一块太抽象了。。
本题是给定颜色种数c和环上的珠子数n,问有多少种染色方案(通过旋转和翻转相同算同一种)最后的结果不会int类型数据表示的范围。
要考虑两种情况:
1.旋转。
将环顺时针旋转i格后,循环节个数为gcd(n,i), 染色方案为 ∑c^gcd(n,i) 其中 i=1,2,3,4,....n
2.翻转。
这里也得考虑两种情况。
当n为奇数时,共有n个循环节个数为(n/2+1)的循环群,还有的资料上说是环的个数为(n/2+1) ,注意这是计算机上的表示,n/2整型相除计算机得到的是整数,其实应该写成(n+1)/2。,染色方案为 n*c^(n/2+1)
为什么n个循环节个数为(n/2+1)的循环群呢?我的理解是这样的,或许不太对。。。
拿正三角形为例,给它三个顶点染色, 对称轴是一个顶点与其对边终点连线所在的直线,这样的直线有3(n=3,即n个顶点) 条,共有3(n)个循环群。假设第一个顶点在对称轴上,那么第二个顶点经过对称轴翻转肯定和第三个顶点重合,那么 (2,3)是一个循环节,(1)自己是一个循环节,循环节个数为2,即(n+1/2)。
当n为偶数时,共有n个循环群,其中有n/2个的循环节个数为(n/2 +1), 有n/2个的循环节个数为(n/2)。
拿正方形为例,四个顶点从左上角顺时针编号1,2,3,4.
当以1,3顶点连线所在直线为对称轴时(对角的两个顶点),这样对称轴有2个(n/2),经过翻转,2,4 重合,1和1重合,3和3重合,那么循环节的个数为3(2,4) (1)(3), 即(n/2+1)。 染色方案为 (n/2)*c^(n/2+1)
当以两条相对平行的边的中点连线所在直线为对称轴时,比如以线段1,2的中点和3,4的中点连线的所在直线为对称轴,这样的对称轴有两个(n/2),经过翻转,1,2重合,3,4重合,循环节的个数为2,(1,2)(3,4),即(n/2)。,也就是谁和谁重合,谁就和谁在一个循环节里。染色方案为(n/2)*c^(n/2)
代码:
#include <iostream> #include <string.h> using namespace std; int c,n;//c种颜色,n个珠子 int ans; int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } int power(int p,int n) { int ans=1; while(n) { if(n&1) ans*=p; p*=p; n/=2; } return ans; } int main() { while(cin>>c>>n&&(c||n)) { ans=0; for(int i=1;i<=n;i++) ans+=power(c,gcd(n,i)); if(n&1)//是奇数,有n个包含(n/2+1)个循环节的循环群 ans+=n*power(c,n/2+1); else ans+=(power(c,n/2+1)+power(c,n/2))*(n/2); ans/=2*n;//别忘了处以置换群的总个数 cout<<ans<<endl; } return 0; }