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

 

Sample Output

 

果然又是一道神题目，用到的知识点真心多且有用。

 

快速幂+费马小定理+巧妙的思路

 

费马小定理：假如p是质数，且(a,p)=1，那么 a^(p-1) ≡1（mod p）因此 a * a^(p-2)  ≡1（mod p），即 a的乘法逆元是a^(p-2)

因此题目需要求组合数：( n!/m!(n-m)! ) mod p =[ n! mod p ]*[ (m! mod p)^(p-2) mod p]*[ ((n-m)! mod p)^(p-2) mod p] mod p

 

多搞几个数据，可以发现，只需找到最少翻动牌个数与最多翻动牌个数即可，中间的状态是连续的，剩下就是排列的问题了。

因为每次翻一张牌，则正面增加1，反面减1，因此翻动的牌数是偶数变化的，又翻的牌可以随机，所以其最多与最少翻动牌数中间每隔一个都是允许出现的情况。

 

官方题解：

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

因为如果对同一张牌进行两次操作，牌的状态不改变。故牌的翻转次数一定是减少偶数次。如果所有数的和是奇数，那么最终结果也一定是奇数。同理，偶数也是一样的。

所以只要递推求出最后的区间，计算sum（C（xi，m）（i=0，1，2。。。）），m是总牌数，xi是在区间内连续的奇数或偶数，在模10^9+9就是最终的答案。

#include <cstdio>

#include <iostream>

#include <cmath>

#define Mod 1000000009

#define max(x,y) ((x)>(y)?x:y)

#define min(x,y) ((x)<(y)?x:y)

using namespace std;

long long J[];

int n,m,a[],l,r,nl,nr;

void Predo(){

    J[]=;

    for(int i=;i<=;i++)

        J[i]=(J[i-]*i)%Mod;

}

long long Q(long long a,long long p){

    int e[],k=;

    while(p){

        e[k++]=p%;

        p=p/;

    }

    long long tmp=;

    for(int i=k-;i>=;i--)

        if(e[i]) tmp=((tmp*tmp)%Mod*a)%Mod;

        else tmp=(tmp*tmp)%Mod;

    return tmp;

}

long long C(int n,int m){

    return ((J[n]*Q(J[m],Mod-))%Mod*Q(J[n-m],Mod-))%Mod;

}

int main()

{

    Predo();

    while(scanf("%d%d",&n,&m)!=EOF){

        for(int i=;i<n;i++){

            scanf("%d",&a[i]);

        }

        int l=r=a[];

        for(int i=;i<n;i++){

            nl=min(abs(l-a[i]),abs(r-a[i]));

            if(l<=a[i]&&a[i]<=r){

                if((a[i]-l)%==) nl=;

                else nl=;

            }

            nr=max(l+a[i]<=m?l+a[i]:*m-l-a[i] , r+a[i]<=m?r+a[i]:*m-r-a[i]);

            if(m-r<=a[i]&&a[i]<=m-l){

                if((a[i]-(m-r))%==) nr=m;

                else nr=m-;

            }

            l=nl;

            r=nr;

        }

        long long ans=;

        for(int i=l;i<=r;i=i+)

            ans=(ans+C(m,i))%Mod;

        printf("%lld\n",ans);

    }

    return ;

}