HDU 4869 Turn the Pokers 另一種區間維護解法

問題重述

同 HDU 4869：m 張牌，n 次翻轉，每次翻 Xi 張，求最終不同狀態數模 1,000,000,009。

區間維護邏輯

維護當前可能正面朝上牌數的區間 [l, r]。初始 l=r=0。每次翻轉 x：

• 新上界：若 r+x ≤ m 則 r+x；若 l+x ≤ m 則按奇偶取 m 或 m-1；否則 2m - l - x。
• 新下界：若 l-x ≥ 0 則 l-x；若 r-x ≥ 0 則按奇偶取 0 或 1；否則 x - r。
• 區間內所有值奇偶性相同，由 x 的奇偶決定翻轉。

組合數快速冪求模

預處理 C(m, k) 利用逆元：C(m,k) = C(m,k-1) * (m-k+1) * inv(k) mod MOD，inv(k) = k^(MOD-2) mod MOD。

代碼實現

#include <cstdio>
#define MOD 1000000009
#define ll long long
ll n, m, a[100005], C[100005];
ll mod_pow(ll a, ll b) { ll r=1; for(;b;b>>=1,a=a*a%MOD) if(b&1) r=r*a%MOD; return r; }
int main() {
    while (~scanf("%lld%lld", &n, &m)) {
        ll l=0, r=0;
        for (int i=0; i= 0) nl = l - a[i];
            else if (r - a[i] >= 0) nl = ((l + a[i]) & 1) ? 1 : 0;
            else nl = a[i] - r;
            l = nl; r = nr;
        }
        C[0]=1;
        for (int k=1; k<=m; ++k)
            C[k] = (m-k < k) ? C[m-k] : C[k-1]*(m-k+1)%MOD * mod_pow(k, MOD-2)%MOD;
        ll ans=0;
        for (ll i=l; i<=r; i+=2) ans = (ans + C[i]) % MOD;
        printf("%lld\n", ans);
    }
    return 0;
}