Polya定理：設G={π1，π2，π3........πn}是X={a1，a2，a3.......an}上一個置換群，用m中顏色對X中的元素進行涂色，那么不同的涂色方案數(shù)為：1/|G|*(m^C(π1)+m^C(π2)+m^C(π3)+...+m^C(πk)).?其中C(πk)為置換πk的循環(huán)節(jié)的個數(shù)。

Polya定理的基礎應用。

你得算出旋轉(zhuǎn)和翻轉(zhuǎn)時，每種置換的循環(huán)節(jié)數(shù)。

旋轉(zhuǎn)時，每種置換的循環(huán)節(jié)數(shù)為gcd（n，i）；

翻轉(zhuǎn)時，若n為奇數(shù)，共有n個循環(huán)節(jié)數(shù)為n+1>>1的置換，

若n為偶數(shù)，共有n/2個循環(huán)節(jié)數(shù)為n+2>>1的置換和n/2個循環(huán)節(jié)數(shù)為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; }

轉(zhuǎn)載于:https://www.cnblogs.com/autsky-jadek/p/6680449.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的【数论】【Polya定理】poj1286 Necklace of Beads的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。