最后的结果中正面向上的奇偶性是一定的，计算出正面向上的范围low，up

结果即为 C(m，low）+ C(m，low+2) +.... + C(m,up) ，用逆元取模

Turn the pokers

3 4
3 2 3
3 3
3 2 3

8
3

Hint
For the second 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)
 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long int LL;

const int maxn=110000;
const LL mod=1000000009LL;

LL a[maxn],n,m;

void ex_gcd(LL a,LL b,LL &d,LL &x,LL &y)
{
	if(!b)
	{
		d=a; x=1; y=0;
	}
	else
	{
		ex_gcd(b,a%b,d,y,x);
		y-=a/b*x;
	}	
}

LL lower,upper;

void cal(LL lower,LL upper)
{
    LL cur=1LL,t=0,ret=0;
    while(t<=upper)    
    {
        if(t>=lower&&t<=upper)
            if((t-lower)%2==0)
                ret=(ret+cur)%mod;    
        t++;
        cur=(cur*(m-t+1))%mod;
        LL d,x,y;
        ex_gcd(t,mod,d,x,y);
        x=(x+mod)%mod;
        cur=(cur*x)%mod;
    }
    cout<<ret<<endl;
}

int main()
{
while(cin>>n>>m)
{
    lower=upper=0LL;
    for(int i=0;i<n;i++)
        cin>>a[i];
    lower=upper=a[0];
    for(int i=1;i<n;i++)
    {
        LL last_low=lower,last_up=upper;

        ///get low bound
        if(a[i]<=last_low)
            lower-=a[i];
        else if(a[i]<=last_up)
            lower=0+((a[i]+last_up)%2==1);
        else
            lower=a[i]-last_up;

        ///get upper bound
        if(a[i]+last_up<=m)    
            upper=a[i]+last_up;
        else if(a[i]+last_low<=m)
            upper=m-((a[i]+last_low)%2==1);
        else
            upper=m-(a[i]+last_low-m);
    }
    cal(lower,upper);
}
    return 0;
}

HDOJ 4869 Turn the pokers,布布扣,bubuko.com

HDOJ 4869 Turn the pokers

原文：http://blog.csdn.net/ck_boss/article/details/38071133