HDU 3037 Saving Beans
传送门
Problem Description
Although winter is far away, squirrels have to work day and night to save beans. They need plenty of food to get through those long cold days. After some time the squirrel family thinks that they have to solve a problem. They suppose that they will save beans in different trees. However, since the food is not sufficient nowadays, they will get no more than beans. They want to know that how many ways there are to save no more than beans (they are the same) in trees.
Now they turn to you for help, you should give them the answer. The result may be extremely huge; you should output the result modulo , because squirrels can’t recognize large numbers.
Input
The first line contains one integer , means the number of cases.
Then followed lines, each line contains three integers , means that squirrels will save no more than same beans in different trees, , and is guaranteed to be a prime.
Output
You should output the answer modulo .
Sample Input
2
1 2 5
2 1 5
Sample Output
3
3
Hint
For sample , squirrels will put no more than beans in one tree. Since trees are different, we can label them as and so on.
The ways are: put no beans, put bean in tree and put beans in tree . For sample , the ways are: put no beans, put bean in tree and put bean in tree .
Translation
有 棵松树,每棵树上的松果都足够多,我们需要采不多于 颗松果,问有多少种取法。每颗松果都是相同的, 棵树是不同的。答案对质数 取模。
Idea
设一共采 颗松果, 且 ;第 棵树上采 颗松果,,那么有 。相当于将 个相同的球放入 个不同箱子且允许有空箱子。
先考察将 个相同的球放入 个不同箱子且不允许有空箱子的情况。可利用插板法,要将 个相同分成 份,就要在 个球的 个空隙中插入 块隔板。因此,答案为 。
如果给每个箱子一个球,就可以把问题转化为不能空的情况了。问题等价于将 个相同的球放入 个不同的箱子且不允许空箱子。因此,将 个相同的球放入 个不同箱子且允许有空箱子的方法数为 。
由于总共采的果子不超过 ,即 ,所以不同的取法有 种。
题目答案为 。此处 较大,且 为质数,考虑使用卢卡斯定理。
Code
1 |
|