HDU 4372：Count the Buildings （Stirling数）

HDU 4372：Count the Buildings （Stirling数）

Count the Buildings

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1300    Accepted Submission(s): 422

Problem Description

There are N buildings standing in a straight line in the City, numbered from 1 to N. The heights of all the buildings are distinct and between 1 and N. You can see F buildings when you standing in front of the first building and looking forward, and B buildings when you are behind the last building and looking backward. A building can be seen if the building is higher than any building between you and it. Now, given N, F, B, your task is to figure out how many ways all the buildings can be.

Input

First line of the input is a single integer T (T<=100000), indicating there are T test cases followed. Next T lines, each line consists of three integer N, F, B, (0

Output

For each case, you should output the number of ways mod 1000000007(1e9+7).

Sample Input

23 2 23 2 1

Sample Output

2 1

N座高楼，高度均不同且为1~N中的数，从前向后看能看到F个，从后向前看能看到B个，问有多少种可能的排列数。首先我们知道一个结论：n的环排列的个数与n-1个元素的排列的个数相等，因为P(n,n)/n=(n-1)!。可以肯定，无论从最左边还是从最右边看，最高的那个楼一定是可以看到的.假设最高的楼的位置固定，最高楼的编号为n，那么我们为了满足条件，可以在楼n的左边分x-1组，右边分y-1组，且用每组最高的那个元素代表这一组，那么楼n的左边，从左到右，组与组之间最高的元素一定是单调递增的，且每组中的最高元素一定排在该组的最左边，每组中的其它元素可以任意排列（相当于这个组中所有元素的环排列）。右边反之亦然。然后，可以这样考虑这个问题，最高的那个楼左边一定有x-1个组，右边一定有y-1个组，且每组是一个环排列，这就引出了第一类Stirling数（n个人分成k组，每组内再按特定顺序围圈的分组方法的数目）。我们可以先把n-1个元素分成x-1+y-1组，然后每组内部做环排列。再在所有组中选取x-1组放到楼n的左边。

所以答案是ans(n, f, b) = C[f + b - 2][f - 1] * S[n - 1][f + b - 2];

AC代码：

#include#include#include#include#include#define INF (1<<30)#define LL long longusing namespace std;const int MMAX = 2100 ;const LL mod = 1e9+7;LL c[MMAX][MMAX],s[MMAX][MMAX];void init() //第一类Stirling数{ for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。