NYOJ 280 LK的项链 &&POJ 2409 Let it Bead(polya 定理)

NYOJ 280 LK的项链  :​​click here​​

POJ 2409 Let it Bead:​​click here​​

题意：一盒有红、蓝、绿三种颜色的珠子，每种颜色珠子的个数都大于24，现在LK想用这一盒珠子穿出一条项链，项链上的珠子个数为n（0<=n<=24）,请你帮她计算一下一共可以用这一盒珠子可以穿出多少条不同的项链。通过旋转、翻转达到同一种状态的被认为是相同的项链。

poj 上是c种颜色，s个珠子组成，数据比24小。

思路：今天刚接触到polya 定理：

Polya定理:设G是n个对象的一个置换群,用m种颜色涂染这n个对象,则不同染色的方案数L=1/|G|*[m^p(a1)+m^p(a2)+....+m^p(an)].其中p(ai)是某个置换的循环数.

1.旋转置换.

我们假设依次顺时针旋转1~n个,则循环个数=gcd(i,n);

2.翻转置换

当n为偶数时,分两种情况,一种是中心轴在两个对称对象上,则循环个数为n/2+1,另一种是对称轴两边分别有n/2个对象,则循环个数为n/2;

当n为奇数时,对称轴就只能在一个对象上,则循环个数为n/2+1;

刚开始接触，不敢说完全的弄懂，有些知识还稍微了解，一知半解，以后多多接触此类的题目，争取搞明白

代码：

两个都一样，poj把3改为c就可以

#include #include #include #include #include #include using namespace std;int gcd(int a,int b){ return b==0?a:gcd(b,a%b);}long long polya(int n,int m){ if(n==0)return 0; long long sum=0; for(int i=1; i<=n; i++) //旋转的时候 sum+=pow(double(m),double(gcd(n,i))); //翻转的时候 if(n&1)sum+=n*pow(double(m),double((n+1)/2));//为奇数 else sum+=n/2*(pow(double(m),double((n+2)/2))+pow(double(m),double(n/2)));//偶数的两种情况 return sum/(2*n);}int main(){ int n; while(~scanf("%d",&n)&&n!=-1) { printf("%d\n",polya(n,3)); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。