# 题解 - [ZOJ 3638] Fruit Ninja

## 原始题面

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

### Sample Output

1 | 3 |

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

1 | /* |