hdu4869 Turn the pokers 2014 Multi-University Training Contest 1

Turn the pokers

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 669    Accepted Submission(s): 231

Problem Description During summer vacation,Alice stay at home for a long time, with nothing to do. She went out and bought m pokers, tending to play poker. But she hated the traditional gameplay. She wants to change. She puts these pokers face down, she decided to flip poker n times, and each time she can flip Xi pokers. She wanted to know how many the results does she get. Can you help her solve this problem?  

Input The input consists of multiple test cases. 

Each test case begins with a line containing two non-negative integers n and m(0<n,m<=100000). 

The next line contains n integers Xi(0<=Xi<=m).  

Output Output the required answer modulo 1000000009 for each test case, one per line.  

Sample Input

3 4
3 2 3
3 3
3 2 3
        

Sample Output

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)
   
    
        

Author FZU  

Source 2014 Multi-University Training Contest 1  

Recommend We have carefully selected several similar problems for you:   4871  4869  4868  4867  4866   

求翻牌的所有可能性 

這道題要求一個正面牌數量的一個區間(mi,ma),則mi,mi+2,mi+4....ma-2,ma都是存在的，然後用組合數求一下，難點在統計最大值和最小值，其次就是組合數了。要用到費馬小定理，通過模的逆元，再用一個快速幂就可以了。

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int mod= 1000000009;
long long c[111111];
long long ans;
int n,m,a,ma,mi,p,q;
long long pow_mod(long long  a,int b)
{
    long long s=1;
    while(b)
    {
        if(b&1)s=s*a%mod;
        a=a*a%mod;
        b=b>>1;
    }
    return s;
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        ma=mi=0;
        for(int i=0;i<n;i++){
            scanf("%d",&a);
            if(mi>=a)p=mi-a;
            else if(ma>=a)p=((mi&1)==(a&1)?0:1);
            else p=a-ma;
            if(ma+a<=m)q=ma+a;
            else if(mi+a<=m)q=(((mi+a)&1)==(m&1)?m:m-1);
            else q=2*m-(mi+a);
            mi=p;ma=q;
        }
        ans=0;
        c[0]=1;
        if(mi==0) ans+=c[0];
        for(int k=1;k<=ma;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>=mi&&(k&1)==(mi&1))ans+=c[k];
        }
        printf("%I64d\n",ans%mod);
    }
    return 0;
}