首页 > 代码库 > HDU4372-Count the Buildings（第一类Stirling数+组合计数）

HDU4372-Count the Buildings（第一类Stirling数+组合计数）

2024-07-19 11:19:38   224人阅读

Count the Buildings

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


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<N, F, B<=2000) described above.
 

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
 
题意：n个房子在一条线上(n<=2000)，高度分别为1~n，现在需要将房子这样放置：从最左往右能看到F个房子，从最右往左能看到B个房子，能看到的条件是 两者之间的房子都要低于这个房子。问这样的方案数。

思路：可以考虑现将最高的拿出来，那么可以考虑左边需要有F-1个房子成递增关系，那么可以将左边的房子分成F-1个组（环），右边有B-1个房子成递减关系，也是如此，这就让人YY到了第一类Stirling数，第一类Stirling数s(p,k)是将将p个物体排成k个非空循环排列的方法数（k个排列是有先后顺序的）。可以想到，每一组都是有顺序的（与环等价）。除此之外，还要计算组合数，就是在(F-1+B-1)组中取出F-1个到左边，乘上即是答案。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 2000+10;
const int MOD = 1000000007;
int n,f,b;
ll s[maxn][maxn];
ll c[maxn][maxn];
void init(){
	c[0][0] = 1;
	s[0][0] = 1;
	for(int i = 1; i < maxn; i++){
		c[i][0] = c[i][i] = 1;
		s[i][0] = 0;s[i][i] = 1;
		for(int j = 1; j < i; j++){
			c[i][j] = (c[i-1][j] + c[i-1][j-1])%MOD; 
			s[i][j] = ((i-1)*s[i-1][j]+s[i-1][j-1])%MOD; 
		} 
	}
}
int main(){
	int ncase;
	init();
	cin >> ncase;
	while(ncase--){
		scanf("%d%d%d",&n,&f,&b); 
		if(f+b-2>n){
			puts("0");
		}else {
			ll ans = (c[f+b-2][f-1]*s[n-1][b+f-2])%MOD; 
			printf("%I64d\n",ans);
		}
	}
	return 0;
}


HDU4372-Count the Buildings（第一类Stirling数+组合计数）


联系
我们