大意：给出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)
思路：要说清楚不是非常easy。官方题解是这么说的：
“终于的结果一定是连续出现的，仅仅须要求出终于的区间。
由于假设对同一张牌进行两次操作，牌的状态不改变。故牌的翻转次数一定是降低偶数次。假设全部数的和是奇数，那么终于结果也一定是奇数。同理，偶数也是一样的。
所以仅仅要递推求出最后的区间，计算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;
}