Turn the pokers

大意：给出n次操作，给出m个扑克，然后给出n个操作的个数a[i]，每个a[i]代表可以翻的扑克的个数，求最后可能出现的扑克的组合情况。

Hint

Sample Input：

3 3

3 2 3

For the this example:

0 express face down,1 express face up

Initial state 000

The first result:000->111->001->110

The second result:000->111->100->011

The third result:000->111->010->101

So, there are three kinds of results(110,011,101)

思路：要说清楚不是很容易。官方题解是这么说的：

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

因为如果对同一张牌进行两次操作，牌的状态不改变。故牌的翻转次数一定是减少偶数次。如果所有数的和是奇数，那么最终结果也一定是奇数。同理，偶数也是一样的。

所以只要递推求出最后的区间，计算sum（C（xi，m）（i=0，1，2。。。）），m是总牌数，xi是在区间内连续的奇数或偶数，在模10^9+9就是最终的答案。”

#define LL long long

const int MOD = 1000000009;
LL J[100005];

void Init()
{///初始化阶乘表
    J[0] = 1;
    for(int i = 1; i <= 100005; ++i){
        J[i] = J[i-1]*i%MOD;
    }
}

///快速幂取模
LL modexp(LL a,LL b,LL n)
{
    LL ret=1;
    LL tmp=a;
    while(b)
    {
       if(b&1) ret=ret*tmp%n;
       tmp=tmp*tmp%n;
       b>>=1;
    }
    return ret;
}
///求组合数 逆元 C(n, m) = n! * (m!*(n-m)!)^(MOD-2)
LL C(LL n, LL m)
{
    return J[n]*modexp(J[m]*J[n-m]%MOD, MOD-2, MOD)%MOD;
}

int a[100010];

int main()
{
    int n, m;
    Init();
    while(~scanf("%d%d", &n, &m))
    {
        for(int i = 0; i < n; ++i)
        {
            scanf("%d", &a[i]);
        }
        int l = 0;
        int r = 1;
        int t = 0;
        for(int i = 0; i < n; ++i)
        {
            int ll = min(abs(l-a[i]), abs(r-a[i]));
            if(l <= a[i] && r >= a[i])
            {
                ll = 0;
            }
            int rr = max(m-abs(l+a[i]-m), m-abs(r+a[i]-m));
            if(l <= m-a[i] && r >= m-a[i])
            {
                rr = m;
            }

            t = (t+a[i])%2;
            l = ll;
            r = rr;
        }
        long long ans = 0;
        for(int i = l; i <= r; ++i)
        {
            if(i%2 == t)
            {
                ans += C(m, i);
                ans %= MOD;
            }
        }
        printf("%I64d\n", ans);
    }

    return 0;
}

//官方题解的解组合
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<cmath>
using namespace std;
int a[100005];
__int64 pmod = 1000000009;
__int64 inv[100005];
__int64 ba[100005];
__int64 rba[100005];
#define M 100005
void pre() {
	inv[0] = inv[1] = 1;
	ba[0] = ba[1] = 1;
	rba[0] = rba[1] = 1;
	for (int i = 2; i < M; i++) {
		inv[i] = ((pmod - pmod / i) * inv[pmod % i]) % pmod;
		ba[i] = (ba[i - 1] * i)%pmod;
		rba[i] = (rba[i - 1] * inv[i])%pmod;
	}
}
__int64 C(int n, int k) {
	return (ba[n] * rba[k] % pmod )* rba[n - k] % pmod;
}