学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4869

题目大意：

有N张牌，一开始全是盖着的。M次操作，每次可以从中任意选择翻 xi 张牌。问最后的状态有多少种。

解题思路：

最终的结果一定是连续出现的，只需要求出最终的区间。

因为如果对同一张牌进行两次操作，牌的状态不改变。故牌的翻转次数一定是减少偶数次。如果所有数的和是奇数，那么最终结果也一定是奇数。同理，偶数也是一样的。所以只要递推求出最后的区间，计算sum（C（xi，m）（i=0，1，2。。。）），m是总牌数，xi是在区间内连续的奇数或偶数，在模10^9+9就是最终的答案。

代码：

const int mod = 1000000009;
using namespace std;
typedef long long ll;
long long quickpow(long long a, long long b) {
    if (b < 0) return 0;
    long long ret = 1;
    a %= mod;
    while(b) {
        if (b & 1) ret = (ret * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ret;
}
//费马小定理求逆元（M必须是质数）
long long INV(long long a) {
    return quickpow(a, mod - 2);
}
ll fac[100010];
int main () {
    int n, m;
    int x, l, r;
    fac[0] = 1;
    for (int i = 1; i <= 100000; i++) fac[i] = (fac[i - 1] * i) % mod;
    while(scanf("%d%d", &n, &m) != EOF) {
        l = 0, r = 1;
        int nl, nr, k = 0;
        for(int i = 0; i < n; ++i) {
            scanf("%d", &x);
            nl = min(abs(l - x), abs(r - x));
            if (l <= x && x <= r) nl = 0;
            nr = max(m - abs(l + x - m), m - abs(r + x - m));
            if (l + x <= m && m <= r + x) nr = m;
            l = nl, r = nr, k = (k + x) % 2;
        }

        ll ans = 0;
        ll tmp;
        for (int i = l; i <= r; i++) if (i % 2 == k) {
            tmp = fac[m] * INV(fac[m - i] * fac[i] % mod) % mod;
            ans += tmp;
            ans %= mod;
        }
        printf("%I64d\n", ans);
    }
    return 0;
}