首页 > 代码库 > hdu 4869 Turn the pokers(递推&组合数学&逆元)

hdu 4869 Turn the pokers(递推&组合数学&逆元)

2024-07-14 18:03:46   222人阅读

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<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
 

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<max。使得v+xi=m。如果都不满足的话说明只能把m-min个0全变为1然后再把多的部分变为0了。min递推同理。然后由于每个位置时等价的。然后就是组合数求可能性了。由于要取模所以要用逆元。
详细见代码：
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
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<n;i++)
        {
            scanf("%d",&x);
            nmi=miv,nma=mav;
            if(x<=miv)
                nmi-=x;
            else if(x<=mav)
                nmi=(mav&1)^(x&1);
            else
                nmi=x-mav;
            if(x<=m-mav)
                nma+=x;
            else if(x<=m-miv)
                nma=m-((mav&1)^(x&1)^(m&1));
            else
                nma=2*m-x-miv;
            mav=nma,miv=nmi;
        }
        for(i=miv;i<=mav;i+=2)
        {
            tp=(base[m-i]*base[i])%mod;
            tp=inv(tp,mod);
            ans+=(base[m]*tp)%mod;
            ans%=mod;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}



联系
我们