POJ 2409 Let it Bead - Polya 計數定理應用

• G = 二面體群，|G| = 2n
• k(g) = 置換 g 的循環數（等價類數）

群元素分類與循環數

合併公式

ans = ( Σ_{i=0}^{n-1} c^{gcd(n,i)}          // 旋轉
      + (n%2 ? n * c^{n/2+1}                // 奇數翻轉
           : n/2 * c^{n/2+1} + n/2 * c^{n/2} ) // 偶數翻轉
      ) / (2*n)

快速冪模板

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

完整參考代碼（C++）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll c, n;
    while (cin >> c >> n) {
        if (c == 0 && n == 0) break;
        ll sum = 0;
        // 旋轉
        for (ll i = 0; i < n; ++i) sum += qpow(c, gcd(n, i));
        // 翻轉
        if (n & 1) sum += n * qpow(c, n/2 + 1);
        else sum += (n/2) * qpow(c, n/2 + 1) + (n/2) * qpow(c, n/2);
        cout << sum / (2*n) << '\n';
    }
    return 0;
}

關鍵細節

• 整數除法：n/2 在 C++ 中自動向下取整，符合公式。
• 溢位：題目未給模數，c,n 範圍不明，但 POJ 原題通常在 64 位有符號範圍內（c≤10, n≤20 左右）。若更大需大整數或取模。
• gcd(0,n)=n：i=0 時對應恆等旋轉，循環數 n，公式自動涵蓋。

數學直覺補充

• 旋轉 i 步將項鍊分成 gcd(n,i) 個循環，每循環長度 n/gcd(n,i)，同色才不變 → c^gcd(n,i) 種不變染色。
• 翻轉對稱軸：奇數 n 每軸過一頂點一邊中點 → 1 個固定點 + (n-1)/2 對 → (n+1)/2 循環；偶數 n 分兩類軸（過頂點/過邊中點），循環數分別 n/2+1、n/2。