Turn the pokers
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1279 Accepted Submission(s): 466
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
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
HintFor 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
Recommend We have carefully selected several similar problems for you: 4896 4895 4894 4892 4891 题意： 一个长度为m的01序列开始时全是0。然后进行n次操作。第i次操作你可以选xi个位置。然后把0
编程1,1变成0.最后问操作后可能有多少不同的序列。
思路： 可以狠明确的是。∑Xi的奇偶性一定和最后1的个数相同。因为最后为0的位置一定被翻转了偶数次。1的位置肯定被翻转了奇数次。然后我们会发现最后1的个数是一个区间。{x|min<=x<=max&&x%2==min%2}。这个可以递推。对于这两个值怎么递推呢。假设我们知道处理完前i-1次操作。当前序列最大1的个数为max,最小1的个数为min。如果xi<=m的话。那么最多1肯定为max+xi。因为我们把这xi次造作全部作用在0的位置就行了。如果xi<=m-min说明我们一定可以找到一个值min<=v
#include
#include
#include
#include
using namespace std; const int INF=0x3f3f3f3f; const int maxn=100010; typedef long long ll; const ll mod=1e9+9; ll base[maxn],ans,tp; void gcd(ll a,ll b,ll& d,ll& x,ll& y)//扩展的欧几里德 { if(!b) d=a,x=1,y=0; else gcd(b,a%b,d,y,x),y-=x*(a/b); } ll inv(ll a,ll n)//求逆元 { ll x,y,d; gcd(a,n,d,x,y); return d==1?(x+n)%n:-1; } int main() { int n,m,i,x,miv,mav,nmi,nma; for(i=base[0]=1;i<=1e5;i++) base[i]=(base[i-1]*i)%mod; while(~scanf("%d%d",&n,&m)) { scanf("%d",&x); ans=0,miv=mav=x; for(i=1;i
|