POJ 1286 Necklace of Beads：Polya 計數定理應用

題目描述

用紅、藍、綠三種顏色給 n (< 24) 個珠子組成的項鏈著色。旋轉或翻轉後相同視為同一種。求本質不同著色方案數。

Polya 定理公式

設群 G 為二面體群 D_n（n 次旋轉 + n 次翻轉，共 2n 個置換）。每種置換的循環指數決定固定著色數。最終答案：

Ans = (1 / (2n)) * [ Σ_{i=0}^{n-1} 3^{gcd(n,i)} + 翻轉貢獻 ]

翻轉貢獻

• n 為奇數：n 次翻轉，每次 1 個珠子固定，其餘 (n-1)/2 對對稱 → n * 3^{(n+1)/2}。
• n 為偶數：n/2 次翻轉過對邊中點（無固定珠，n/2 對） → (n/2) * 3^{n/2}；n/2 次翻轉過對頂點（2 個固定珠，(n-2)/2 對） → (n/2) * 3^{n/2+1}。總和：(n/2) * (3^{n/2} + 3^{n/2+1})。

C++ 代碼實現

#include <cstdio>
#include <cmath>
using namespace std;

long long pow3(int exp) {
    long long res = 1, base = 3;
    while (exp) {
        if (exp & 1) res *= base;
        base *= base;
        exp >>= 1;
    }
    return res;
}

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

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n != -1) {
        long long sum = 0;
        // 旋轉
        for (int i = 0; i < n; ++i)
            sum += pow3(gcd(n, i));
        // 翻轉
        if (n & 1)
            sum += (long long)n * pow3(n / 2 + 1);
        else
            sum += (long long)(n / 2) * (pow3(n / 2) + pow3(n / 2 + 1));
        printf("%lld\n", sum / (2 * n));
    }
    return 0;
}

關鍵點

1. 使用 64 位整數（long long）防止溢出，3^23 ≈ 9.4e10 仍在範圍內。
2. 快速冪計算 3^k。
3. 輸入以 -1 結束，多組測試。