POJ 1286 Necklaces of Beads - Burnside 引理計算項鏈本質不同染色數

問題描述

用 3 種顏色給 n 個珠子的項鏈染色，考慮旋轉和翻轉對稱。求本質不同的染色方案數。n ≤ 20（實際可大），多組輸入以 -1 結束。

Burnside 引理 (Polya 計數)

對稱群為二面體群 D_{2n}，包含 n 次旋轉和 n 次翻轉。方案數 = (Σ_{g∈G} 3^{c(g)}) / (2n)，其中 c(g) 是置換 g 的循環數。

• 旋轉：旋轉 k 位置，循環數 = gcd(n, k)。貢獻 Σ_{k=0}^{n-1} 3^{gcd(n,k)}。
• 翻轉：
  • n 奇數：每次翻轉固定 1 個珠子，其餘 (n-1)/2 對交換，循環數 = 1 + (n-1)/2 = (n+1)/2。共 n 次翻轉，貢獻 n * 3^{(n+1)/2}。
  • n 偶數：n/2 次翻轉固定 2 個珠子（循環數 2 + (n-2)/2 = n/2+1），n/2 次翻轉固定 0 個珠子（循環數 n/2）。貢獻 (n/2)*3^{n/2+1} + (n/2)*3^{n/2}。

代碼實現

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;

LL qpow(LL a, int k) {
    LL r = 1;
    while (k) { if (k&1) r *= a; a *= a; k >>= 1; }
    return r;
}
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }

LL rotation(int n) {
    LL sum = 0;
    for (int k = 0; k < n; ++k) sum += qpow(3, gcd(n, k));
    return sum;
}
LL reflection(int n) {
    if (n & 1) return (LL)n * qpow(3, (n+1)/2);
    return (LL)(n/2) * qpow(3, n/2) + (LL)(n/2) * qpow(3, n/2+1);
}

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n != -1) {
        LL ans = (rotation(n) + reflection(n)) / (2*n);
        printf("%lld\n", ans);
    }
    return 0;
}