POJ 2409 Let it Bead：Polya 計數定理在項鍊染色問題中的應用

題目大意

用 c 種顏色給 n 個珠子的項鍊染色。項鍊可旋轉、翻轉。求本質不同的染色方案數。

Polya 計數定理核心公式

方案數 = (1/|G|) · Σ_{g∈G} c^{cycles(g)}

• G：對稱群（旋轉 + 翻轉），|G| = 2n
• cycles(g)：置換 g 的循環數（等價類數）

置換類型分析

完整 C++ 代碼

#include 
#include 
using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

ll qpow(ll a, ll n) {
    ll r = 1;
    while (n) {
        if (n & 1) r *= a;
        a *= a;
        n >>= 1;
    }
    return r;
}

int main() {
    ll c, n;
    while (~scanf("%lld%lld", &c, &n)) {
        if (c == 0 && n == 0) break;
        ll ans = qpow(c, n);  // 恆等旋轉
        for (int i = 1; i < n; i++)  // 非恆等旋轉
            ans += qpow(c, gcd(n, i));
        if (n & 1)  // n 奇數
            ans += n * qpow(c, n/2 + 1);
        else {  // n 偶數
            ans += (n/2) * qpow(c, n/2 + 1);
            ans += (n/2) * qpow(c, n/2);
        }
        printf("%lld\n", ans / (2*n));
    }
    return 0;
}

關鍵點解析

1. 旋轉置換循環數：旋轉 i 步將 n 個位置分為 gcd(n,i) 個循環，每個循環長 n/gcd(n,i)
2. 翻轉置換分奇偶：
   • 奇數 n：每條對稱軸過一個珠子和對面邊中點，固定 1 個珠子 + (n-1)/2 對 → (n+1)/2 = n/2+1 個循環
   • 偶數 n：n/2 條軸過對頂兩珠子 → n/2+1 循環；n/2 條軸過對面邊中點 → n/2 循環
3. 快速冪：cⁿ 可能很大，用二進制快速冪 O(log n)
4. 整除性：理論保證總和能被 2n 整除，用整數運算無誤差

樣例驗證

Input:
3 4
0 0

c=3, n=4
旋轉: 3⁴ + 3^{gcd(4,1)} + 3^{gcd(4,2)} + 3^{gcd(4,3)} = 81 + 3 + 9 + 3 = 96
翻轉: 2×3^{4/2+1} + 2×3^{4/2} = 2×27 + 2×9 = 72
總和 = 168, 除以 2n=8 → 21
Output: 21

擴展與變體

• 僅旋轉不翻轉：群大小 n，公式簡化為 (1/n) Σ c^{gcd(n,i)} (Necklace 問題)
• 帶權重顏色：用生成函數替代 c^{cycles}
• 三維對稱：立方體染色，群大小 24
• Burnside 引理：Polya 定理的特例，僅計數不枚舉模式

學習建議

Polya 計數是組合數學神器，核心步驟：

1. 確定對稱群 G 及其大小
2. 分類群元素類型，計算每類循環數
3. 套用公式求和除以 |G|
4. 注意奇偶、邊界情況分類

推薦資料：《組合數學》(盧開澤)、Polya 原著《Combinatorial Enumeration》、在線課程 MIT 6.042J。