POJ 2409 Let it Bead：Polya 計數項鏈著色

題目描述

同 POJ 1286，項鏈 n 顆珠，c 種顏色，旋轉翻轉視為同一。求本質不同著色數。多組輸入，n=0,c=0 結束。

Polya 公式模板

Ans = (1/(2n)) * [ Σ_{d|n} φ(d) * c^{n/d}  +  翻轉項 ]
// 翻轉項：
// n 奇：n * c^{(n+1)/2}
// n 偶：(n/2) * (c^{n/2} + c^{n/2+1})

其中 φ 為歐拉函數。旋轉部分利用 Burnside 引理：長度為 d 的旋轉有 φ(d) 個，每個固定 c^{n/d} 種著色。

C++ 代碼實現

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

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

ll phi(ll x) {
    ll res = x;
    for (ll i=2; i*i<=x; ++i)
        if (x%i==0) { res = res/i*(i-1); while(x%i==0) x/=i; }
    if (x>1) res = res/x*(x-1);
    return res;
}

int main() {
    int n, c;
    while (cin >> c >> n, n||c) {
        ll sum = 0;
        // 旋轉
        for (int d=1; d<=n; ++d)
            if (n%d==0) sum += phi(d) * mod_pow(c, n/d);
        // 翻轉
        if (n&1) sum += (ll)n * mod_pow(c, n/2 + 1);
        else sum += (ll)(n/2) * (mod_pow(c, n/2) + mod_pow(c, n/2 + 1));
        cout << sum / (2*n) << endl;
    }
    return 0;
}

關鍵點

• 無模數要求，直接用 64 位整數（c≤10, n≤100 時最大值 < 2^63）。
• 歐拉函數 φ(d) 計算利用質因子分解。
• 快速冪 mod_pow 計算 c^k。