Total Submission(s): 196    Accepted Submission(s): 51

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)

 

Source

 

题意：

输入操作次数n和扑克牌数m，一開始扑克牌全都背面朝上。如今输入n个数xi，表示每次选择xi张牌翻转。问最后的牌的情况有多少种可能。

思路：

背面为0。正面为1。如果最后能出现x个1，由于每一个牌都是一样的，所以最后x个1的情况有C(m,x)个。

如今问题转化为求最后可能出现几个1。

最后的结果奇偶性同样，由于将1个翻转0变为1个翻转1,1的个数会添加2，反之降低2。

最后的结果肯定是一个连续的奇数或者偶数区间，不可能有间断点，原理同上。

如今的任务就是如何找最大最小值了，假设这次能出现[le,ri]的区间，如今要翻转x次，假设x<=le，那么下次的最小值mi就是le-x了，假设x>le&&x<ri的话，假设le、x同奇偶，mi=0，否则为1，假设x>ri的话，那么mi=x-ri。最大值同理。递推可得到最后的区间。

如今就是要计算C(m,x)了。能够由C(m,0)递推得到，可是涉及到除法，须要用逆元。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <string>

#include <map>

#include <stack>

#include <vector>

#include <set>

#include <queue>

#define maxn 235

#define MAXN 100005

#define mod 1000000009

#define INF 0x3f3f3f3f

#define pi acos(-1.0)

#define eps 1e-8

typedef long long ll;

using namespace std;

ll n,m,ans,flag,cnt,tot;

ll fac[100005],rev[100005];

ll pow_mod(ll a,ll i,ll n)  // 高速幂取模

{

    if(i==0)return 1%n;

    ll temp=pow_mod(a,i>>1,n);

    temp=temp*temp%n;

    if(i&1)temp=temp*a%n;

    return temp;

}

void init() // 初始化

{

    fac[0]=rev[0]=1;

    for(ll i=1;i<=100000;i++)

    fac[i]=fac[i-1]*i%mod,rev[i]=pow_mod(fac[i],mod-2,mod);

}

ll C(ll n,ll m) // 求组合数取mod的值

{

    return (fac[n]*rev[m]%mod)*rev[n-m]%mod;

}

int main()

{

    ll i,j,t,x,le,ri;

    init();

    while(~scanf("%I64d%I64d",&n,&m))

    {

        le=ri=0;

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

        {

            scanf("%I64d",&x);

            ll u,v;

            if(x<=le) u=le-x;

            else if(x>le&&x<ri)

            {

                if((x+le)%2==0) u=0;

                else u=1;

            }

            else u=x-ri;

            if(x<=m-ri) v=ri+x;

            else if(x>m-ri&&x<=m-le)

            {

                if((x+le+m)%2==0) v=m;

                else v=m-1;

            }

            else v=le+(m-le)-(x-(m-le));

            le=u,ri=v;

        }

       // printf("le:%I64d ri:%I64d\n",le,ri);

        ans=0;

        for(i=le;i<=ri;i+=2)

        {

            ans+=C(m,i);

            ans%=mod;

        }

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

    }

    return 0;

}