[HDU4372] Count the Buildings

前言

第一类斯特林数，有思维难度

题目

HDU

讲解

考虑最高的那栋房子会被两边计算，除去它，还剩(n-1)栋房子

左边能看见的有(F-1)栋房子，右边能看见(B-1)栋房子

我们先考虑左边一边

如果我们选出了能被看见的(F-1)栋房子，剩下的所有高度小于它们的房子都会在它们的右边

对于每一栋选出的房子都会形成一条长龙，后面跟的就是高度小于它的房子，但不一定高度小于它的房子刚好跟在它后面

把这个看作一组，发现这一组便是第一类斯特林数中的一个环(重难点)

我们总共需要(F-1+B-1)个这样的环，方案数即为(s[n-1][F+B-2])，这里的(s)数组是第一类斯特林数

然后我们要在(F+B-2)个环中选出(F-1)个放在左边，顺序为根据排头高度递增

所以答案还要乘上(C_{F+B-2}^{F-1})

最终的答案即为(s[n-1][F+B-2]*C_{F+B-2}^{F-1})

记得判无解

代码

int C[MAXN][MAXN],s[MAXN][MAXN];
void pre(int x)
{
	s[0][0] = C[0][0] = 1;
	for(int i = 1;i <= x;++ 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] = (s[i-1][j-1] + 1ll * (i-1) * s[i-1][j]) % MOD;
	}
}

int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	pre(2000);
	for(int T = Read(); T ;-- T)
	{
		n = Read();F = Read();B = Read();
		if(F+B-2 > n-1) {Put(0,'
');continue;}
		Put(1ll * s[n-1][F+B-2] * C[F+B-2][F-1] % MOD,'
');
	}
	return 0;
}