首页 > 代码库 > TOJ-1341 Let it Bead
TOJ-1341 Let it Bead
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 Specification
Every line of the input file defines a test case and contains two integers: the number of available colors c followed by the length of the bracelets s. Input is terminated by c=s=0. Otherwise, both are positive, and, due to technical difficulties in the bracelet-fabrication-machine, cs≤32, i.e. their product does not exceed 32.
Output Specification
For each test case output on a single line the number of unique bracelets. The figure below shows the 8 different bracelets that can be made with 2 colors and 5 beads.
|
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: University of Ulm Local Contest 2000
这道题用到组合数学中的polya定理。关于群论的知识我只是在之前学离散数学还是密码学时浅尝辄止，到用的时候也是捉襟见肘。
Polya定理：设G={π1，π2，π3........πn}是X={a1，a2，a3.......an}上一个置换群，用m中颜色对X中的元素进行涂色，那么不同的涂色方案数为：
(mC(π1)+mC(π2)+mC(π3)+...+mC(πk))/|G|. 其中C(πk)为置换πk的循环节的个数。
以我目前的水平分析这个抽象的公式实在是毫无办法，我稍微分享一下我的局限的结合题目的理解。
这道题可以理解为是用c种颜色给环状摆放的珠子着色，并且如果两种着色方案可以通过旋转或者翻转珠子的摆放互相变换，则只能算一种着色，求总共的着色种数。
举一个简单的例子，用c种颜色给摆成正方形的4个珠子着色。4个珠子标号1，2，3，4。显然有如下8种置换（从左上顶点处顺时针）：
1. 1234 2. 4123 3. 3412 4. 2341 （旋转置换）
5. 1432 6. 3214 7. 4321 8. 2143 （翻转置换）
对置换1的4个珠子着c种颜色考虑标号不同有c^4种，在本题中，着色rgbw与着色gbwr只能算是同一种（置换1变换为2），所以对这种着色种数除以置换数即为本
题着色种数（即公式中分母的|G|）。但是有的着色方案比如rrrr，在所有的置换中情况都是一样的，在本题中应算做一种着色，然而我们在计算c^4/|G|时，把这种着色
的计数变为了1/8。这种问题是出现在各种置换间变换中由循环节引起的着色数丢失。解决办法就是在分子上把丢掉的计数补上，比如着色rrrr，应在分子上为2到7每种
置换加1，则除以|G|得到的即为本题中其应为的着色种数。
对于旋转置换2-4，将其与置换1上下对齐，置换1的一个数对应另一个置换中同位置的一个数，则两个置换对应的数会构成循环节，如置换1和2，珠子1，2，3，4构
成一个循环节；置换1和3，珠子1和3，2和4构成2个循环节。对于置换1和其他旋转置换的循环节着相同的颜色，两种置换中情况相同，故对一个旋转置换，应在分子上加
c^k，k为该置换循环节数。
对于翻转置换，若以对角线和对边中位线为轴翻转，各有2种翻转。以对角线为轴，则两对角顶点各为一个循环节，其他每一对对称点为一个循环节；以对边中位线为
轴，每一对对称点为一个循环节。若是奇数边正多边形，以顶点及其对边中点连线为轴。
对于置换1和其他置换的循环节着相同的颜色，两种置换中情况相同，故对一个置换，应在分子上加c^k，k为该置换循环节数。
以上即为对Polya定理在本题中的理解。
同时我们得知，在已知颜色数c和珠子数n的情况下，我们只需求珠子摆成正n边形的置换数和各种置换的循环节数即可求解此题。
显然对于n，旋转置换算及初始摆放顺序（如上例置换1）共n种，若某种置换是初始顺序旋转i次所得，其循环节数为gcd（n,i）。翻转置换数也为n，且若n为奇数，每
种置换有（n+1）/2个循环节；若n为偶数，以对角线和对边中位线为轴翻转两类置换各n/2种，分别有n/2+1和n/2个循环节。
总结公式即为ans = (∑(i=1,n)c^gcd(n,i) + n*c^(n+1)/2)/2n ……n为奇数
ans = (∑(i=1,n)c^gcd(n,i) + (n/2)*(c^(n/2+1)+c^(n/2)))/2n ……n为偶数
#include <iostream> using namespace std; int c,n; int ans; int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } int power(int a,int n) { int t=1; while(n) { if(n&1) t*=a; a*=a; n/=2; } return t; } int main(){ int c,n,ans; while(cin>>c>>n,c,n) { ans=0; for(int i=1;i<=n;i++)//旋转时有n个置换群 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; }
TOJ-1341 Let it Bead