版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: 题解 - [ZOJ 3638] Fruit Ninja categories:
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
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
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
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
3
0
21
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)$