hdu 4869

Turn the pokers

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

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?

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 typedef long long ll;
 9 
10 const int MAX = 1e5 + 7;
11 const int MOD = 1e9 + 9;
12 int N, M;
13 int x[MAX];
14 ll c[MAX];
15 
16 ll mod_pow(ll x, ll n, ll mod) {
17         ll res = 1;
18         while (n > 0) {
19                 if (n & 1) res = res * x % mod;
20                 x = x * x % mod;
21                 n >>= 1;
22         }
23 
24         return res;
25 }
26 
27 void solve() {
28         int Min = 0, Max = 0;
29         for (int i = 1; i <= N; ++i) {
30                 int t1, t2;
31                 if (Min >= x[i]) {
32                         t1 = Min - x[i];
33                 } else if (x[i] <= Max) {
34                         t1 = !((Min & 1) == (x[i] & 1));
35                 } else {
36                         t1 = x[i] - Max;
37                 }
38 
39                 if (Max + x[i] <= M) {
40                         t2 = Max + x[i];
41                 } else if (Min + x[i] <= M) {
42                         t2 = (((Min + x[i]) & 1) == (M & 1)) ? M : M - 1;
43                 } else {
44                         t2 = 2 * M - (Min + x[i]);
45                 }
46 
47                 Min = t1; Max = t2;
48         }
49 
50         //printf("min = %d max = %d
", Min, Max);
51         ll ans = 0;
52         c[0] = 1;
53         if (Min == 0) ans += 1;
54         for (int i = 1; i <= Max; ++i) {
55                 if (M - i < i) c[i] = c[M - i];
56                 else
57                 c[i] = c[i - 1] * (M - i + 1) % MOD * mod_pow(i, MOD - 2,MOD) % MOD;
58                 if (i >= Min && (i & 1) == (Min & 1)) ans = (ans + c[i]) % MOD;
59 
60         }
61 
62         printf("%I64d
", ans);
63 }
64 int main()
65 {
66     while (scanf("%d%d", &N, &M) != EOF) {
67             for (int i = 1; i <= N; ++i) {
68                     scanf("%d", &x[i]);
69             }
70 
71             solve();
72     }
73     //cout << "Hello world!" << endl;
74     return 0;
75 }

View Code

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

首先1个个数的奇偶性和翻牌次数的奇偶性相同，然后根据分类讨论找出出现的最少的1 和最多的1，最终的结果肯定是连续的奇数或者偶数

然后求出sum(c(M,i)) ( Min < i <= Max)连续的奇数或偶数

根据费马小定理可以知道若p为质数，gcd(a, p） = 1,则a ^ (p - 2) = 1 / p （mod p）根据这个求出组合数就可以了

Recommend

We have carefully selected several similar problems for you: 4871 4868 4867 4866 4865