HDU 4869 Turn the pokers

HDU 4869

Turn the pokers

Turn the pokers

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 394 Accepted Submission(s): 140

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

其实就是求最后状态有几个可能翻转，然后就是组合数了。 有几个翻转是连续的区间，而且奇偶性和总和是一样的。 递推求出区间，然后求解。   一开始区间是\[0,0\] 递推的时候把几种情况都罗列一下，就得出了下一个区间。

/* ***************

Author        :kuangbin

Created Time  :2014/7/23 8:54:58

File Name     :HDU4869.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

const int MAXN = 100010;

const int MOD = 1e9+9;

long long pow_m(long long a,long long n,long long mod)

{

	long long ret = 1;

	long long tmp = a%mod;

	while(n)

	{

		if(n&1)ret = ret*tmp%mod;

		tmp = tmp*tmp%mod;

		n >>= 1;

	}

	return ret;

}

long long inv(long long a,long long mod)

{

	return pow_m(a,mod-2,mod);

}

long long C[MAXN];

long long INV[MAXN];

int main()

{

    //freopen("1009.in","r",stdin);

    //freopen("out.txt","w",stdout);

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

		INV[i] = inv(i,MOD);

	int n,m,a;

	while(scanf("%d%d",&n,&m) == 2)

	{

		C[0] = 1;

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

		{

			C[i] = C[i-1](m-i+1)%MODINV[i]%MOD;

		}

		int l = 0, r = 0;

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

		{

			scanf("%d",&a);

			int tmp1 = min(m-l,a);

			int nr = l+tmp1-(a-tmp1);

			int tmp2 = min(r,a);

			int nl = r-tmp2+(a-tmp2);

			if(nl > nr)swap(nl,nr);

			if(l <= a && a <= r)

			{

				if(l%2 == a%2)

					nl = 0;

				else nl = min(nl,1);

			}

			if((m-r) <= a && a <= (m-l))

			{

				if((m-l)%2 == a%2)

					nr = m;

				else nr = max(nr,m-1);

			}

			if(l >= a)nl = min(nl,l-a);

			if(m-r >= a)nr = max(nr,r+a);

			l = nl;

			r = nr;

		}

		int ans = 0;

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

		{

			ans += C[i];

			if(ans >= MOD)ans -= MOD;

		}

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

	}

    return 0;

}