学步园

题意：输入操作次数n和扑克牌数m，一开始扑克牌全都背面朝上。现在输入n个数xi，表示选择xi张牌翻转，问最后的牌的情况有多少种可能？

题解：

我们将一开始的牌认为是m个0，而翻转就是将0变成1或者1变成0。最后的答案就是ans=∑C(m,k)，C(m，k)为组合数，k为所有能取到的1的可能个数。详细的解释，先了解最后1的个数的奇偶性，跟所有翻牌数的和的奇偶相同（每次翻牌，要么0->1，要么1->0，都是在改变1的个数奇偶）。之后我们需要找到最少有i个1，以及最大有j个1；i的情况就是有1就翻1，j的情况就是有0就翻0，而中间的情况时，取偶数步数，一半翻0，一半翻1，保持不变，所以可以确定i,i+2,i+4,...,j-2,j都能被翻到。最后ans=∑C(m,k)（i<=k<=j&&k%2==i%2）。

 【注】以为要多高深的知识，结果就是暴力！

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;

#define LL __int64
const int maxn=1e5+10;
const int mod=1e9+9;
LL c[maxn];
LL pow_mod(LL a,int b)
{
    LL s=1;
    while(b)
    {
        if(b&1)s=s*a%mod;
        a=a*a%mod;
        b=b>>1;
    }
    return s;
}
int main()
{
    int n,m;
    //freopen("C:\\Documents and Settings\\Administrator\\桌面\\in.txt","r",stdin);
    //freopen("C:\\Documents and Settings\\Administrator\\桌面\\out.txt","w",stdout);
    //printf("%I64d\n",pow_mod(2,10));
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int i,j,k,x,p,q;
        i=j=0;
        for(k=0;k<n;k++)
        {
            scanf("%d",&x);
            //求最小1的个数i
            if(i>=x)p=i-x;
            else if(j>=x)p=((i&1)==(x&1)?0:1);
            else p=x-j;
            //求最大1的个数j
            if(j+x<=m)q=j+x;
            else if(i+x<=m)q=(((i+x)&1)==(m&1)?m:m-1);
            else q=2*m-(i+x);
            i=p;j=q;
            //printf("**%d %d\n",i,j);
        }

        LL ans=0;
        c[0]=1;
        if(i==0)ans+=c[0];
        for(k=1;k<=j;k++)
        {
            if(m-k<k)c[k]=c[m-k];
            else c[k]=c[k-1]*(m-k+1)%mod*pow_mod(k,mod-2)%mod;
            if(k>=i&&(k&1)==(i&1))ans+=c[k];
        }
        printf("%I64d\n",ans%mod);
    }
    return 0;
}