Turn the pokers

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

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)

题解

假设第i次操作后有x1个1，第i+1次操作x2个数，假设在xi中操作了i个数，在n-xi中操作了j个数，i+j=x2;操作后有Z个1，

则有 Z=x1-i+j=x1-i+x2-i=x1+x2-2i;其中i€[0,min(x1,x2)]

1,x1>=x2,z 属于 [x1-x2,x1+x2],

2,x1<x2, z 属于 [x2-x1,x1+x2],

x1+x2>n格外处理。区间左端点的奇偶性相同。处理后看最后的区间就行，然后就是组合。

由于数据相当大，所以要将组合中的除法变成乘法，C(n， m) = n!/(m!*(n-m)!)，由费马小定理：若p是质数， a^(p-1) = 1%p，那么，a^(p-2) = 1/a%p，利用这个公式，得到1/(m!*(n-m)!) = (m!*(n-m)!)^(p-2) mod p，即C(n, m) = n!*(m!*(n-m)!)^(p-2) mod p，这样就可以变除为乘。而求(n-m)!)^(p-2 )mod p中用快速幂简化运算

最终的结果一定是连续出现的，只需要求出最终的区间。

sum+=((f[m]%mod)*(quickmod((f[i]*f[m-i])%mod,mod-2)%mod))%mod

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define mod 1000000009
#define LL __int64
#define maxn 100000+5

LL f[maxn];

void set()
{
    int i;
    f[0] = 1;
    for(i = 1; i<maxn; i++)
        f[i] = (f[i-1]*i)%mod;
}

LL quickmod(LL a,LL b)
{
    LL ans = 1;
    while(b)
    {
        if(b&1)
        {
            ans = (ans*a)%mod;
            b--;
        }
        b/=2;
        a = ((a%mod)*(a%mod))%mod;
    }
    return ans;
}

int main()
{
    int n,m,i,j,k,l,r,x,ll,rr;
    set();
    while(~scanf("%d%d",&n,&m))
    {
        l = r = 0;
        for(i = 0; i<n; i++)
        {
            scanf("%d",&x);
            //计算最小的1的个数，尽可能多的让1->0
            if(l>=x) ll = l-x;//当最小的1个数大于x，把x个1全部翻转
            else if(r>=x) ll = ((l%2)==(x%2))?0:1;//当l<x<=r，由于无论怎么翻，其奇偶性必定相等，所以看l的奇偶性与x是否相同，相同那么知道最小必定变为0，否则变为1
            else ll = x-r;//当x>r,那么在把1全部变为0的同时，还有x-r个0变为1
            //计算最大的1的个数,尽可能多的让0->1
            if(r+x<=m) rr = r+x;//当r+x<=m的情况下，全部变为1
            else if(l+x<=m) rr = (((l+x)%2) == (m%2)?m:m-1);//在r+x>m但是l+x<=m的情况下，也是判断奇偶，同态那么必定在中间有一种能全部变为1，否则至少有一张必定为0
            else rr = 2*m-(l+x);//在l+x>m的情况下，等于我首先把m个1变为了0，那么我还要翻（l+x-m）张，所以最终得到m-(l+x-m)个1

            l = ll,r = rr;
        }
        LL sum = 0;
        for(i = l; i<=r; i+=2)//使用费马小定理和快速幂的方法求和
            sum+=((f[m]%mod)*(quickmod((f[i]*f[m-i])%mod,mod-2)%mod))%mod;
        printf("%I64d
",sum%mod);
    }

    return 0;
}