HDU 4869 Turn the Pokers：群論視角下的翻牌遊戲

問題描述

有 m 張撲克牌面朝下（0），進行 n 次翻轉操作，第 i 次翻轉 X_i 張牌。求所有可能的最終狀態數，模 1,000,000,009。

核心抽象：阿貝爾群上的區間維護

每張牌狀態為 0/1，翻轉即加法模 2。定義集合 M(n, k) 為 n 張牌中恰有 k 張為 1 的所有狀態集合。翻轉 x 張牌的操作可視為在群 G = ∪ M(n, k) 上的乘法 *。該運算滿足：

• 結合律、交換律
• 單位元 M(n,0)
• 逆元即自身（翻兩次等於不翻）

因此 (G, *) 是阿貝爾群。多次翻轉等價於群元素連乘。

區間與奇偶性推導

考慮 M(n, x1) * M(n, x2)（設 x1 ≥ x2）。結果為公差為 2 的等差數列：

M(4,3)*M(4,2) = M(4,1) + M(4,3)
M(8,5)*M(8,3) = M(8,2)+M(8,4)+M(8,6)+M(8,8)

規律：結果區間 [L, R] 且所有元素奇偶性相同。奇偶性由 x1, x2 奇偶決定（XOR 關係）。

連乘多項時，只需維護當前區間 [low, high] 和奇偶標記 isOdd，每步 O(1) 更新：

• 新區間下界：min(|low - x|, |high - x|) 或 0
• 新區間上界：對稱計算
• 奇偶性：isOdd ^= (x & 1)

組合數計算

最終答案為區間內符合奇偶性的 C(m, k) 之和。預處理階乘、逆元階乘（模 1,000,000,009），利用費馬小定理 a⁻¹ ≡ a^(p-2) (mod p) 計算逆元，單次查詢 O(1)。

複雜度

O(n) 維護區間 + O(m) 求和，總 O(n+m) 每測試用例，完美通過。

參考代碼片段

const int MOD = 1000000009;
ll inv[MAXM], fac[MAXM], rfc[MAXM];
void init() {
    inv[1] = fac[0] = fac[1] = rfc[0] = rfc[1] = 1;
    for (int i=2; i<MAXM; ++i) {
        inv[i] = (MOD - MOD/i) * inv[MOD%i] % MOD;
        fac[i] = fac[i-1] * i % MOD;
        rfc[i] = rfc[i-1] * inv[i] % MOD;
    }
}
inline ll C(int n, int k) { return fac[n] * rfc[k] % MOD * rfc[n-k] % MOD; }

pair<int,int> update(int x, pair<int,int> cur, bool& isOdd) {
    isOdd ^= (x & 1);
    int L = cur.first, R = cur.second;
    int low = (L <= x && x <= R) ? 0 : min(abs(L-x), abs(R-x));
    x = n - x;
    int high = (L <= x && x <= R) ? n : max(n - abs(L-x), n - abs(R-x));
    return {low, high};
}