Turn the pokers





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

Total Submission(s): 316    Accepted Submission(s): 101









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)

题目大意

给定M张牌，能够翻转N次。每次能够翻转恰好Xi张牌。刚開始牌面所有朝下，问经过N次翻转之后可能产生的扑克序列数（如例子hint）。

解题思路

现场还是没出……想到dp的思路但复杂度高达N^2.

能够观察到，我们最后正面朝上的牌的数量奇偶总是一定的（如1，3。5），由于不同奇偶情况就须要至少多翻一次，但翻动的次数已经固定不能更改。

考虑一次翻转，最多X1张牌正面朝上了。最少也是X1张。

假设第二次仅仅翻转1张，再设1<X1<m 则最多会有X1+1张牌正面朝上，最少会有X1-1张牌正面朝上。

如今如果我们已经翻好k-1次

最多a张正面朝上，最少b张正面朝上

假设b>=Xk 则翻转后最少有b-Xk张正面朝上（其余的情况能够一次翻一张正面的，一张反面的。情况保持不变）。

否则。假设a>Xk。这时最少会有0张或1张正面朝上（依据a和Xk的奇偶性推断），

再否则，最少会有Ak-a张正面朝上（先把正面朝上的所有翻转，剩下的再翻便是最少张数）

关于最大值的讨论同理

最后关于组合数的计算，因为m固定不变，就能够依据组合数公式C(m,n)=C(m-1,n)*(n-m+1)/m 线性求解。因为1e9+9是大素数。除法操作可用逆元求解取代。

#include <cstdio>

#define LL long long

int n,m;

LL mod=1000000009;

LL a[100005];

void egcd(LL a,LL b,LL &x,LL &y)

{

  if (b==0)

  {

    x=1;y=0;

    return ;

  }

  egcd(b,a%b,x,y);

  LL t=x;

  x=y,y=t-a/b*y;

  return;

}

LL cal(LL x,LL y)

{

  LL cur=1,tmp=0,t=0;

  while(t<=y)

  {

    if (t>=x&&t<=y)

    if ((t-x)%2==0) tmp=(tmp+cur)%mod;

    t++;

    cur=cur*(m-t+1)%mod;

    LL t1,t2;

    egcd(t,mod,t1,t2);

    t1=(t1+mod)%mod;

    cur=cur*t1%mod;

  }

  return tmp;

}

int main()

{

  while (~scanf("%d%d",&n,&m)){

  LL upper,lower,plower,pupper;

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

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

  upper=lower=pupper=plower=0;

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

  {

    if (plower>=a[i]) lower-=a[i];

    else if (pupper>=a[i]) lower=0+((pupper+a[i])%2==1);

    else lower=a[i]-pupper;

    if (pupper+a[i]<=m) upper+=a[i];

    else if (plower+a[i]<=m) upper=m-((plower+a[i])%2==1);

    else {upper=m-(plower+a[i]-m);}

    plower=lower;//plower代表上一步的最小值

    pupper=upper;//pupper代表上一步的最大值

  }

    printf("%I64d\n",cal(lower,upper));

  }

  return 0;

}