题解 - [ZOJ 3638] Fruit Ninja

发表于 更新于 分类于 ， 本文字数： 715 阅读时长 ≈ 3 分钟

题目链接

原始题面

Fruit Ninja is a famous game all over world and Edward seems to be good at it. However, after broke the record many a time, Edward thought that it's too easy to get high score in that game, and that it must be more challenging to write a game like Fruit Ninja. Soon, Edward began his new program Fruit Ninja made in China

According to Edward's design, there are exactly n kinds of fruit in the game, and exactly m fruits will appear on the screen at the beginning of a new game. What's more, to make the display of the game more colorful, for some kinds of fruits, there are limits to their amount. For example, Edward may make a rule that the amount of apple displayed on the screen should be less than \(3\), and that of peach should be greater than \(1\)

As a math-lover at the same time, Edward wants to know the total number of combination of the fruits displayed on the screen at the beginning of a game

Input

The input contains multiple test cases, seperated by an empty line

The first line of each test case contains two positive integer n, the number of different kinds of fruit, and m, the number of fruits that will appear on the screen at the beginning of a game. Then follows k (k ≤ n) lines describe the limits to some fruits. The decription is a line in certain format "[FruitName]: [less|greater] than [x]", which means the amount of [FruitName] should be less(greater) than [x] ([x] is an integer in range \([0, 10000000]\))

For all tests cases, \(0 ≤ n ≤ 16, 1 ≤ m ≤ 10000000\), and we ensure that fruitnames in the decriptions will be all different and make up of only lower case latin latters, and its length is less than \(10\). \(n = 0\) indicates the end of input, and you should output nothing for this case

Output

For each case, output an integer in a single line: total number(mod \(100000007\)) of combination of the fruits displayed on the screen at the beginning of a game

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
2 5
apple: less than 3
peach: greater than 1

1 18
apple: less than 0

4 10
fan: less than 1
rou: less than 7
tang: less than 6
cai: greater than 4

0 1

Sample Output

1
2
3
3
0
21

Hint

For the first case, there are \(3\) combinations: \(0\) apple and \(5\) peaches, \(1\) apple and \(4\) peaches, \(2\) apples and \(3\) peaches

For the second case, apparently, it's impossible that the amount of apple is below zero. So the answer is \(0\)

Author: LI, Dinghua

题意简述

给定 \(n\), \(m\) 和 \(k\leqslant n\) 个限制条件 (限制条件为某种水果大于或小于某数，\(k\) 未给出), 求在 \(n\) 种水果里满足给定的限制条件下取出 \(m\) 个的取法个数，最后结果对 \(10^8+7\) 取模

解题思路

首先，我们知道在 \(n\) 种元素 (每种不限量) 中一共取 \(m\) 个的取法一共有 \(\binom{n+m-1}{n-1}\) 种

然后就要考虑如何处理限制关系了

对于要求某种元素大于 \(k\) 的情况，我们在取 \(m\) 个时，只需预先取出 \(k+1\) 个，之后无论怎么取都是刚好满足限制的，即只需 m -= k + 1

对于要求某种元素小于 \(k\) 的情况，可以应用容斥定理

另外用 scanf 的朋友们要注意，在 ZOJ 的评测环境上 scanf("%d%d\n", &n, &m); 并不能读掉换行符

复杂度

\(O(n2^n)\)

代码参考

Show code

ZOJ_3638view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <cstdio>
#include <cstring>
const i64 mod = 100000007;
i64 qpow(i64 a, i64 b) {
  i64 res = 1;
  for (; b; b >>= 1, (a *= a) %= mod)
    if (b & 1) (res *= a) %= mod;
  return res;
}
i64 lucas(i64 a, i64 b) {
  if (a < b || a < 0 || b < 0) return 0;
  i64 res = 1, _ = 1;
  for (int i = 0; i < b; i++) {
    res = res * (a - i) % mod;
    _ = _ * (i + 1) % mod;
  }
  return res * qpow(_, mod - 2) % mod;
}
char op[505], line[5005];
int limit[505];
int main() {
  int m, n;
  while (~scanf("%d%d", &n, &m) && (m != 1 || n)) {
    int k = 0, _;
    fgets(line, sizeof(line), stdin);
    while (fgets(line, sizeof(line), stdin) && line[0] != '\n' &&
           line[1] != '\n') {
      sscanf(line, "%*s%s%*s%d\n", op, &_);
      if (op[0] == 'g') m -= _ + 1;
      else limit[++k] = _;
    }
    if (m < 0) {
      puts("0");
      continue;
    }
    i64 ans = 0;
    for (int i = 0; i < (1 << k); ++i) {
      int _ = 0, now = 0;
      for (int j = 1; j <= k; ++j)
        if (i & (1 << j - 1)) {
          ++_;
          now += limit[j];
        }
      ans += (_ & 1 ? -1 : 1) * lucas(n + m - 1 - now, n - 1);
    }
    printf("%lld\n", (ans % mod + mod) % mod);
  }
}