本文主要是介绍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 <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
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;
}
这篇关于NYOJ 280 LK的项链 POJ 2409 Let it Bead(polya 定理)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
