HDU 4869 Turn the pokers

3 43 2 33 33 2 3Sample Output
83          Hint
                  For the second example:0 express face down,1 express face upInitial state 000The first result:000->111->001->110The second result:000->111->100->011The third result:000->111->010->101So, there are three kinds of results(110,011,101)         给出m张牌，每次可以翻动一些牌，问最后牌的可能情况。因为每次都是随便翻的，只要能确定最后有几张牌是正面朝上，那么就可以用组合数直接计算，然后我们可以考虑，正面朝上的可能情况，分为上下界[L,R]显然，LR是同奇偶的，并且中间的间隔都是2，对于可以翻动x张牌的情况，用LR来推算新的上下界，就可以了。
#include<cstdio>#include<cstring>#include<cmath>#include<stack>#include<algorithm>#include<iostream>using namespace std;const int mod=1e9+9;const int N=1e5+10;int n, m, x, ans;int inv[N],g[N],f[N];int c(int x,int y){    return 1LL*f[x]*g[y]%mod*g[x-y]%mod;}int main(){    f[0]=g[0]=1;    for (int i=1;i<N;i++)    {        f[i]=1LL*f[i-1]*i%mod;        inv[i]=i==1?1:1LL*inv[mod%i]*(mod-mod/i)%mod;        g[i]=1LL*g[i-1]*inv[i]%mod;    }    while (~scanf("%d%d",&n,&m))    {        int l=m,r=m;        for (int i=1,j,k;i<=n;i++)        {            scanf("%d",&x);            if (r-x<=0) j=x-r;            else if (l-x>=0) j=l-x;            else j=(r-x)%2;            if (r+x<=m) k=r+x;            else if (l+x>=m) k=2*m-l-x;            else k=(m+j)%2?m-1:m;            l=j; r=k;        }        ans=0;        for (int i=l;i<=r;i+=2) ans=(ans+c(m,i))%mod;        printf("%d/n",ans);    }    return 0;}