自动搬运

查看原文

来自洛谷，原作者为

	newbiechd AFO

搬运于2025-08-24 22:01:54，当前版本为作者最后更新于2018-10-02 19:25:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Blog
早期作品，不喜轻喷。
这应该是斯特林数和组合数的基本应用
我一开始写的题解没有关于斯特林数和组合数的介绍，结果没通过审核，现在加上：

组合数：

大家应该都熟悉它的表达式，但我们这里使用它的递推式会更加方便，下面推导组合数的递推式。设$\binom{n}{m}$表示在$n$个元素中取$m$个的方案数，那么如果我们考虑第$n$个元素取或不取：取的情况就要在剩下的$n-1$个元素中取$m-1$个；不取的情况就要在剩下的$n-1$个元素中取$m$个。由此得到递推式：
$\binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}$

斯特林数：

准确地说是第一类斯特林数，通常用中括号表示，形如$[^{\,n}_{m}]$，表示$n$个人坐$m$张圆桌（没有空桌）的方案个数，我们也只需要考虑递推式。考虑第$n$个人单独坐一张桌子或坐到已经有人的桌子上：如果单独坐一张桌子，前面的$n-1$就要坐$m-1$张桌子；如果坐到已经有人的桌子上，就先让$n-1$个人坐$m$张桌子，第$n$个人可以坐到之前$n-1$个人中任意一个人的左边（其实说右边也无所谓，因为人们坐的是圆桌，这样考虑是为了不重不漏地包含所有的情况）
这样我们就可以得到递推式：
$[^{\,n}_{m}]=[^{\,n-1}_{m-1}]+(n-1)*[^{n-1}_{\,\,\,m}]$

下面进入正题：

首先，高度为$n$的建筑是肯定不会被挡住的，可以把它作为一个分水岭，在它左边的被左边的建筑挡住，在它右边的被右边的建筑挡住。
由此我们可以把所有的建筑分成$A+B-1$个部分，每个部分由这个部分最高的建筑和被他所挡住的建筑组成，高$n$的建筑单独构成一个部分。
那么我们就可以把除了$n$以外的$n-1$个建筑放到$A+B-2$个圆桌上（$n$独坐一个桌），这时就是一个斯特林数。
对于每个圆桌上的建筑，构成了一个圆排列，但由于必须有一个最高的建筑挡住其他的建筑，这个圆排列的起始端就确定了，可以不重不漏地代表一个之前提到的部分。
对于每一个这样的部分，我们只需考虑它是放在$n$的左边还是右边，因此答案再乘上一个组合数就可以了。
答案就是：
$[^{\,\,\,\,\,\,n-1}_{A+B-2}]*\binom{A+B-2}{A-1}$ （中括号表示斯特林数）
我们只需要利用递推式，就可以$O(A*n)$的求出我们所需的斯特林数，$O(A^2)$的求出需要的组合数。 上代码：

#include<cstdio>
#define R register
#define L long long
#define S 50000
#define N 200
using namespace std;
const int mod=1e9+7;
L s[S+10][N+10],c[N+10][N+10];
inline int read(){
	R int f=0;	R char ch=getchar();
	while(ch<48||ch>57) ch=getchar();
	while(ch>47&&ch<58) f=(f<<3)+(f<<1)+(ch^48),ch=getchar();
	return f;
}
int main(){
	R int t=read(),n,a,b,i,j;
	s[0][0]=s[1][1]=1;
	for(i=2;i<=S;++i) s[i][1]=s[i-1][1]*(i-1);
	for(i=0;i<=N;++i) c[i][0]=1;
	for(i=2;i<=S;++i)
		for(j=1;j<=N&&j<=i;++j)
			s[i][j]=(s[i-1][j-1]+s[i-1][j]*(i-1))%mod;//斯特林数递推式
	for(i=1;i<=N;++i)
		for(j=1;j<=N>>1&&j<=i;++j)
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;//组合数递推式
	while(t--){
		n=read(),a=read(),b=read();
		printf("%lld\n",s[n-1][a+b-2]*c[a+b-2][a-1]%mod);
	}
	return 0;
}

我在文中用的斯特林数（中括号）是靠上标下标表示的，效果可能不太好，如果有哪位大佬知道怎么打这种中括号，请在评论区里留言，谢谢！