HDU 3923 Invoker：Polya 計數定理求項鏈染色方案數模 1e9+7

問題描述

有 n 種顏色，m 個珠子排成環（可旋轉、翻轉）。兩種染色若通過旋轉或翻轉重合視為同一種。求本質不同染色方案數模 1,000,000,007。T≤500, n,m≤10000。

Polya 計數：二面體群作用

置換群為二面體群 D_m（2m 個元素）：m 個旋轉 + m 個翻轉。

• 旋轉：旋轉 i 位（i=0..m-1），循環節數 gcd(m,i)，固定染色數 n^{gcd(m,i)}。
• 翻轉：
• m 奇：m 個翻軸，每個循環節數 (m+1)/2，貢獻 m * n^{(m+1)/2}。
• m 偶：m/2 個過頂點翻軸（循環節 m/2+1），m/2 個過邊中點翻軸（循環節 m/2），貢獻 (m/2)*n^{m/2+1} + (m/2)*n^{m/2}。

總和 S = Σ_{rot} + Σ_{flip}，答案 S / (2m) mod P。

模逆元處理除法

模 P 下除以 2m 等價於乘以逆元 inv(2m) = (2m)^{P-2} mod P（費馬小定理，P 為質數）。或用擴展歐幾裡得求逆。

完整參考代碼

#include <cstdio>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
ll qpow(ll a,ll e){
    ll r=1; a%=MOD;
    while(e){ if(e&1) r=r*a%MOD; a=a*a%MOD; e>>=1; }
    return r;
}
ll exgcd(ll a,ll b,ll&x,ll&y){
    if(b==0){ x=1; y=0; return a; }
    ll g=exgcd(b,a%b,x,y);
    ll t=x-(a/b)*y; x=y; y=t; return g;
}
int main(){
    int T; scanf("%d",&T);
    for(int cas=1;cas<=T;cas++){
        ll n,m; scanf("%lld%lld",&n,&m);
        ll ans=0;
        // 旋轉
        for(ll i=1;i<=m;i++) ans=(ans+qpow(n, std::gcd(m,i)))%MOD;
        // 翻轉
        if(m&1) ans=(ans + m%MOD * qpow(n, m/2+1))%MOD;
        else ans=(ans + (m/2)%MOD * (qpow(n,m/2+1)+qpow(n,m/2))%MOD)%MOD;
        // 除以 2m
        ll inv; 
        exgcd(2*m, MOD, inv, inv); // inv 是 2m 的逆元
        inv = (inv%MOD+MOD)%MOD;
        ans = ans * inv % MOD;
        printf("Case #%d: %lld\n", cas, ans);
    }
    return 0;
}

總結

HDU 3923 是 Polya 計數定理在二面體群上的標準應用，關鍵在於正確分類旋轉/翻轉的循環節數、快速冂計算大指數、模逆元處理除法，綜合了組合數學與數論技巧。