hdu 4372 Count the Buildings 轮换斯特林数

题目大意

n栋楼有n个不同的高度

现在限制从前面看有F个点，后面看有B个点

分析

最高那栋楼哪都可以看到

剩下的可以最高那栋楼前面分出F-1个组

后面分出B-1个组

每个组的权值定义为组内最高楼的高度

那么\(\binom {F+B-2}{F-1}\)分好组后，组和组之间的顺序是唯一确定的

而且要满足最高楼前面的组，每组最高楼在最左（不然最高楼左边的组内成员能被看到）

在最高楼后面的组同理

确定好每组最高楼后，剩下的楼可以任意排序

又有这样一个结论： (n-1)个点的排列数=n个点的轮换数

那就是在\(n-1\)栋楼中，轮换数为\(F+B-2\)的方案数

\(ans=\dbinom{F+B-2}{F-1}*\left[\begin{matrix} n-1\\F+B-2\end{matrix}\right]\)

注意

数据F+B-2可能越界

solution

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cmath>

#include <algorithm>

using namespace std;

typedef long long LL;

const int Q=1000000007;

const int M=2003;

inline LL rd(){

	LL x=0;bool f=1;char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

	for(;isdigit(c);c=getchar()) x=x*10+c-48;

	return f?x:-x;

}

int tcas;

LL n,F,B;

LL lh[M][M];

LL c[M][M];

void init(){

	int i,j,k;

	for(i=0;i<M;i++){

		c[i][0]=1;

		for(j=1;j<=i;j++)

			c[i][j]=(c[i-1][j]+c[i-1][j-1])%Q;

	}

	lh[0][0]=1;

	for(i=1;i<M;i++)

	for(j=1;j<=i;j++){

		lh[i][j]=(lh[i-1][j-1]+(i-1)*lh[i-1][j]%Q)%Q;

	}

}

int main(){

	init();

	int i;

	tcas=rd();

	while(tcas--){

		n=rd(),F=rd(),B=rd();

		if(F+B-2>=M) puts("0");

		else printf("%I64d\n",c[F+B-2][F-1]*lh[n-1][F+B-2]%Q);

	}

	return 0;

}