返回首页 返回专题

【HDU4372】Count the Buildings 题解

其实这是一道数学题。下面为了方便，以S(n,k)表示第二类斯特林数

首先，我们考虑到这么一个事实：在两栋可见的高楼之间的所有房子是可以任意排列的

我们知道，a-1个元素的排列等于a个元素的圆排列，于是假设两栋可见高楼间距为a，那么就会有a+1个元素的圆排列种方案

对于每栋高楼，都这么去考虑，最后会发现，假如可见高楼位置是确定的，那么我们要计算的，就是n-1个元素，分成(f-1)+(b-1)组进行圆排列的方案数，减去的那个就是最中间那个高楼

发现就是第一类斯特林数S(n-1,f+b-2)

又容易推出可见高楼的位置分布有C(f+b-2,f-1)种情况

于是答案就是C(f+b-2,f-1)*S(n-1,f+b-2)

#include<bits/stdc++.h>
#define Mod 1000000007
using namespace std;

const int N=2000;
int C[N+10][N+10];
int S[N+10][N+10];

void Init()
{
	S[0][0]=1;
	for(int i=0;i<=N;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;
			S[i][j]=(1ll*(i-1)*S[i-1][j]+S[i-1][j-1])%Mod;
		}
	}
}

int main()
{
	int T,n,f,b;
	Init();
	for(cin>>T;T;T--)
	{
		scanf("%d%d%d",&n,&f,&b);
		int ans=1ll*C[f+b-2][f-1]*S[n-1][f+b-2]%Mod;
		printf("%d\n",ans);
	}
	return 0;
}