首页 > 代码库 > 【Polya定理】poj1286 Necklace of Beads
【Polya定理】poj1286 Necklace of Beads
Polya定理：设G={π1，π2，π3........πn}是X={a1，a2，a3.......an}上一个置换群，用m中颜色对X中的元素进行涂色，那么不同的涂色方案数为：1/|G|*(mC(π1)+mC(π2)+mC(π3)+...+mC(πk)). 其中C(πk)为置换πk的循环节的个数。
Polya定理的基础应用。
你得算出旋转和翻转时，每种置换的循环节数。
旋转时，每种置换的循环节数为gcd（n，i）；
翻转时，若n为奇数，共有n个循环节数为n+1>>1的置换，
若n为偶数，共有n/2个循环节数为n+2>>1的置换和n/2个循环节数为n>>1的置换。
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
int n;
ll Pow(int x,int p){
ll res=1;
for(int i=1;i<=p;++i){
res*=(ll)x;
}
return res;
}
int main(){
while(1){
scanf("%d",&n);
if(n==-1){
break;
}
if(n==0){
puts("0");
continue;
}
ll sum=0;
for(int i=1;i<=n;++i){
sum+=Pow(3,__gcd(n,i));
}
if(n&1){
sum+=(ll)n*Pow(3,n+1>>1);
}
else{
sum+=(ll)(n>>1)*Pow(3,n+2>>1);
sum+=(ll)(n>>1)*Pow(3,n>>1);
}
cout<<sum/(2ll*(ll)n)<<endl;
}
return 0;
}
【Polya定理】poj1286 Necklace of Beads
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。