【数论】【Polya定理】poj1286 Necklace of Beads

Polya定理：设G={π1，π2，π3........πn}是X={a1，a2，a3.......an}上一个置换群，用m中颜色对X中的元素进行涂色，那么不同的涂色方案数为：1/|G|*(m^C(π1)+m^C(π2)+m^C(π3)+...+m^C(π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; }

转载于:https://www.cnblogs.com/autsky-jadek/p/6680449.html

创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的【数论】【Polya定理】poj1286 Necklace of Beads的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。