HDU 4869 Turn the pokers：翻牌遊戲數學推導與組合計數

HDU 4869 Turn the pokers - 翻牌遊戲解題報告

題意：初始 m 張牌背面朝上。n 次操作，第 i 次可選擇恰好 x_i 張牌翻轉。問最終正面朝上的牌數可能有多少種情況（模 1e9+9）。

核心觀察

只需關注最終正面朝上的牌數 k。每次操作將 k 變為 k'，滿足：

• k' = k + (x_i - 2t)，其中 t 為翻轉的正面牌數（0 ≤ t ≤ min(k, x_i)）。
• 即 k' 與 k 同奇偶性，且 |k' - k| ≤ x_i，且 k' ∈ [0, m]。

因此可維護 k 的可行區間 [L, R] 及奇偶性。每次操作更新：

newL = max(0, L - x_i) 或根據奇偶調整
newR = min(m, R + x_i) 或根據奇偶調整

組合數計算

最終答案為 Σ C(m, k) ，k 遍歷可行區間內符合奇偶性的值。預計算階乘及逆元（費馬小定理），O(1) 計算組合數。

代碼關鍵片段

const ll MOD = 1e9+9;
ll fac[maxn], invFac[maxn];
ll C(int n, int m) { return fac[n] * invFac[m] % MOD * invFac[n-m] % MOD; }

void init() {
    L = R = x[0];
    for (i=1..n-1) {
        // 根據 x[i] 更新 L, R
    }
}
ll solve() {
    ll ans = 0;
    for (int k = L; k <= R; k += 2) ans = (ans + C(m, k)) % MOD;
    return ans;
}

複雜度

O(n + m) 預計算，O(n) 更新區間，O(m) 求和（m≤1e5）。