HDU 4869 Turn the pokers(推理)

HDU 4869 Turn the pokers

題目鏈接

題意：給定n個翻轉撲克方式，每次方式對應可以選擇其中xi張進行翻轉，一共有m張牌，問最後翻轉之後的情況數

思路：對於每一些翻轉，如果能確定最終正面向上張數的情況，那麼所有的情況就是所有情況的C(m, 張數)之和，那麼這個張數進行推理會發現，其實會有一個上下界，每隔2個位置的數字就是可以的方案，因為在翻牌的時候，對應的肯定會有牌被翻轉，而如果向上牌少翻一張，向下牌就要多翻一張，奇偶性是不變的，因此只要每次輸入張數，維護上下界，最後在去求和即可

代碼：

#include 
#include 

typedef long long ll;
const ll MOD = 1000000009;
const int N = 100005;
int n, m, num;
ll fac[N];

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {x = 1; y = 0; return a;}
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

ll inv(ll a, ll n) {
    ll x, y;
    exgcd(a, n, x, y);
    return (x + n) % n;
}

ll C(int n, int m) {
    return fac[n] * inv(fac[m] * fac[n - m] % MOD, MOD) % MOD;
}

int main() {
    fac[0] = 1;
    for (ll i = 1; i < N; i++)
	fac[i] = fac[i - 1] * i % MOD;
    while (~scanf("%d%d", &n, &m)) {
	scanf("%d", &num);
	int up = num;
	int down = num;
	for (int i = 1; i < n; i++) {
	    scanf("%d", &num);
	    int up2 = m - down;
	    int down2 = m - up;
	    if (num >= down && num <= up)
		down = ((down&1)^(num&1));
	    else if (num < down) down = down - num;
	    else down = num - up;

	    if (num >= down2 && num <= up2) {
		up = m - ((up2&1)^(num&1));
	    }
	    else if (num < down2) {
		up = m - (down2 - num);
	    }
	    else up = m - (num - up2);
	}
	ll ans = 0;
	for (int i = down; i <= up; i += 2) {
	    ans = (ans + C(m, i)) % MOD;
	}
	printf("%lld\n", ans);
    }
    return 0;
}