hdu4372(第一类斯特林数) Count the Buildings

2017年08月22日 12点热度 0人点赞 0条评论

Count the Buildings

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


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

2
3 2 2
3 2 1
 


Sample Output

2
1
 


Source

/**
大意: 给定一系列楼房,都在一条水平线上,高度从1到n,从左侧看能看到f个, 从右侧看,能看到b个,问有多少种这样的序列。。
思路: 因为肯定能看到最高的,,那我们先假定最高的楼房位置确定,那么在其左边还有f-1个能看见,在其右边还有b-1个,能看见。。所以可以这样将题目转化: 将除最高楼之外的n-1个楼,分成f-1+b-1 组,在最高楼左边f-1 组,在其右边b-1组,那么分成f-1+b-1 组  就是第一类Stirling数。s[n-1][f-1+b-1]。。左边f-1 组,在其右边b-1组,就是将这f-1+b-1 组,组合c(f-1+b-1,f-1)
**/

#include
#include
#include
using namespace std;
#define ll long long
const int mod=1e9+7;
int n,a,b;
ll c[2002][2002],s[2002][2002];
void play_table() {
	c[0][0]=1;
	for(int i=1; i<2001; ++i) {
		c[i][0]=1;//边界条件要注意
		for(int j=1; j<=i; ++j)
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	}

	for(int i=1; i<2001; i++) {
		s[i][0] =0;
		s[i][i]=1;
		for(int j=1; j
未经允许不得转载!hdu4372(第一类斯特林数) Count the Buildings

update

纸上得来终觉浅, 绝知此事须躬行。