来源:http://poj.org/problem?id=2409
题意:就是有一串项链,有几种颜色,问用所给的颜色着色项链,有多少种不同的方案。
思路:赤裸裸的Polya定理啊。这里说下Ploya的公式吧,至于证明,要用到生成函数了。。生成函数我都没看懂,Polya又看了一天,还是不知其所以然。不过对于其中的几个概念倒是知道了。
设奇数方案为X,则X = sigma(pow(color,循环数))/ 2*n,n是项链的长度,其实2*n就是置换群的个数,color是颜色的个数,循环数指的是每种着色集中的循环数,这个也有公式。旋转的时候,其实就是最大公约数了,至于翻转的时候,可以直接算出来。Ploya定理果然是不明白啊,都不知道该怎么说,理解的还是不透彻,仅限于会用公式。
代码:
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
int mi(int x,int y){
int s = 1;
for(int i = 1;i <= y;++i)
s *= x;
return s;
}
int gcd(int a,int b){
if(b == 0)
return a;
return gcd(b,a%b);
}
int main(){
//freopen("1.txt","r",stdin);
int numcolor,len;
while(scanf("%d%d",&numcolor,&len)){
if(numcolor + len == 0)
break;
int sum = 1;
for(int i = 1;i <= len;++i){
int x = gcd(len,i);
sum += mi(numcolor,x);
}
if(len % 2){
sum += (mi(numcolor,(len - 1)/2 + 1) * len);
}
else{
sum += (len/2 * mi(numcolor,len/2 + 1) + len/2 * mi(numcolor,len/2));
}
printf("%d\n",sum / (2 * len));
}
return 0;
}
分享到:
相关推荐
poj 2409 Let it Bead.md
北大POJ1129-Channel Allocation【四色定理】 解题报告+AC代码
POJ 1006 源代码——中国剩余定理分析POJ 1006 源代码——中国剩余定理分析POJ 1006 源代码——中国剩余定理分析
ACM组合数学波利亚计数解析,通过例题解释波利亚计数的简单入门用法。
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
7.组合数学 //Polya定理 8.模拟 9.数据结构 //并查集、堆 10.博弈论 //表示举例 非主流算法: 1.送分题 2.构造 3.高精度 4.几何 5.排序 6.日期/时间处理 (这类题目相当多的) 7.数学方法
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1006-Biorhythms【中国剩余定理】 解题报告+AC代码
北大POJ1159-Palindrome 解题报告+AC代码
POJ 1300 Door Man:无向图、欧拉定理、gets、sscanf
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj分类poj分类poj分类poj分类
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
北大POJ2002-Squares 解题报告+AC代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1048,加强版的约瑟夫问题 难度中等