HDU 4869 Turn the pokers (2014多校联合训练第一场1009) 解题报告（维护区间 + 组合数）

时间：2021-12-01 05:12:53

Turn the pokers

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

Total Submission(s): 108    Accepted Submission(s): 21

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
 

    解题报告：非常奇妙的题目。基本是依照官方解题报告来写的代码。
    简单来说。用 l 和 r 记录最少移动了多少牌，和最多移动了多少牌。最后用组合数求和就是答案。

一张牌翻两次等于没有翻。所以l。r应该是奇偶性同样，且l。r范围内都是解。

    代码例如以下：
#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <queue>

#include <vector>

#include <map>

#include <set>

#include <string>

using namespace std;

#define ff(i, n) for(int i=0;i<(n);i++)

#define fff(i, n, m) for(int i=(n);i<=(m);i++)

#define dff(i, n, m) for(int i=(n);i>=(m);i--)

typedef long long LL;

typedef unsigned long long ULL;

void work();

int main()

{

#ifdef ACM

    freopen("in.txt", "r", stdin);

#endif // ACM

    work();

}

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

const int mod = 1000000009;

int powMod(LL a, int b)

{

    LL res = 1;

    while(b)

    {

        if(b&1)

            res = res*a%mod;

        a=a*a%mod;

        b>>=1;

    }

    return res;

}

int inv[111111];

void work()

{

    // 初始化，求出1-100000在模1000000009系下的逆元

    fff(i, 1, 100000)

        inv[i] = powMod(i, mod-2);

    int n, m;

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

    {

        int l = 0, r = 0;

        int ll, rr;

        ff(i, n)

        {

            int x;

            scanf("%d", &x);

            if(r + x <= m)

                rr = r + x;

            else if(l + x <= m)

                rr = ((m + l + x)&1) ? m-1 : m;

            else

                rr = 2 * m - l - x;

            if(l - x >= 0)

                ll = l - x;

            else if(r - x >= 0)

                ll = ((l + x)&1);

            else

                ll = x - r;

            l = ll, r = rr;

        }

        LL ans = 0;

        LL c = 1;

        fff(i, 0, m)

        {

            if(i == l)

            {

                ans += c;

                l += 2;

                if(l > r) break;

            }

            c = c * (m-i) % mod * inv[i+1] % mod;

        }

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

    }

}

相关文章