題意

用k種顏色對n個珠子構成的環上色，旋轉翻轉后相同的只算一種，求不等價的著色方案數。

思路

---

?

Polya定理

X是對象集合{1, 2, ……, n}， 設G是X上的置換群，用M種顏色染N種對象，則不同的染色方案數為： ? λ(g)表示置換g的輪換個數，且λ(g) = λ1(g) +?λn(g) + …… +?λn(g)，其中λi(g)表示g中長度為i的輪換（循環）個數.

---

? 本題是對一個n個珠子的圓珠的顏色，而圓珠的置換群有： Ⅰ翻轉：1.當n為奇數時，有n種翻轉，每種翻轉的軸都是一個頂點和該頂點對邊中點的連線，有n種置換，每種置換的輪換個數均為(n/2+1)。 2.當n為偶數時，有n種翻轉，其中n/2種轉軸是兩個對應頂點連線，輪換個數為n/2+1；另n/2種轉軸是兩條對邊中點的連線，輪換個數為n/2。 Ⅱ旋轉：枚舉旋轉角度360/n*i，有n種旋轉；第i種旋轉有gcd(n,?i)個輪換，每個輪換的長度都是n/gcd(n,?i)。 然后帶入公式即可.

代碼

? [cpp] #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <string> #include <cstring> #include <vector> #include <set> #include <stack> #include <queue> #define MID(x,y) ((x+y)/2) #define MEM(a,b) memset(a,b,sizeof(a)) #define REP(i, begin, end) for (int i = begin; i <= end; i ++) using namespace std; int gcd(int a, int b){ return b?gcd(b, a%b):a; } int main(){ //freopen("test.in", "r", stdin); //freopen("test.out", "w", stdout); int c, s; while(scanf("%d %d", &c, &s) != EOF){ long long res = 0; if (c + s == 0) break; if (s % 2 == 1){ res += (long long)s * pow(c, s/2+1); } else{ res += (long long)(s/2) * (pow(c, s/2) + pow(c, s/2+1)); } for (int i = 1; i <= s; i ++){ res += (long long)pow(c, gcd(s, i)); } printf("%I64d\n", res/2/s); } return 0; } [/cpp] ?

轉載于:https://www.cnblogs.com/AbandonZHANG/p/4114132.html

總結

以上是生活随笔為你收集整理的POJ 2409 Let it Bead (Polya定理)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。