FJOI 2016 建筑师（斯特林数）

发表于 |
字数统计: 947字 | 阅读时长 ≈ 4min

【FJOI2016】建筑师

问题描述

小 Z 是一个很有名的建筑师，有一天他接到了一个很奇怪的任务：在数轴上建 n 个建筑，每个建筑的高度是 1 到 n 之间的一个整数。

小 Z 有很严重的强迫症，他不喜欢有两个建筑的高度相同。另外小 Z 觉得如果从最左边（所有建筑都在右边）看能看到 A个建筑，从最右边（所有建筑都在左边）看能看到 B 个建筑，这样的建筑群有着独特的美感。现在，小 Z 想知道满足上述所有条件的建筑方案有多少种？

如果建筑 i 的左(右)边没有任何建造比它高，则建筑 i 可以从左(右)边看到。两种方案不同，当且仅当存在某个建筑在两种方案下的高度不同。

输入格式

第一行一个整数 T，代表 T 组数据。
接下来 T 行，每行三个整数 n,A,B

输出格式

对于每组数据输出一行答案 mod10^9+7。

样例输入 1

2
3 2 2
3 1 2

样例输出 1

2
1

样例输入 2

5
1 1 1
2 1 1
4 3 1
10 2 2
8 6 4

样例输出 2

1
0
3
219168
0

提示

对于 10% 的数据 ： 1≤n≤10
对于 20% 的数据 ： 1≤n≤100
对于 40% 的数据 ： 1≤n≤50000, 1≤T≤5
对于 100%的数据 ：1≤n≤50000, 1≤A,B≤100, 1≤T≤200000

直接dp可以拿到40分，令$F[i][j]$表示$i$个数，从一端能看到$j$个递推即可。

标算需要用到第一类斯特林数。

考虑最高的建筑，他一定能被看到，那么他左右两边各还有$A-1,B-1$个建筑能被看到。
左右是对称的，因此先讨论左边，那么显然每一个能被看到的建筑后面可能有一些建筑物被挡住了，考虑将每一个建筑物和他后面被挡住的建筑物，
假设一个建筑物挡住了$d$个建筑，那么他们可能的构成方案有$d!$种，即等价于$d+1$个数，给定了一个数放于队首，其他数随意排列的方案数，等价于$d+1$个数的圆排列数目。

那么总共应该有$A-1$个这样的圆排列，同时考虑右边的情况，问题等价于将$n-1$（不考虑最高的）个数，划分成$A+B-2$个圆排列的方案数，就是第一类斯特林数，记为$S_{n-1}^{A+B-2}$，同时，这样的圆要选$A-1$个放到左边，因此还要乘上$C_{A+B-2}^{A-1}$

因此最后的答案就是$S_{n-1}^{A+B-2}\times C_{A+B-2}^{A-1}$

斯特林数和组合数都递推预处理，可以做到$O(1)$回答，$O(nA+A^2)$预处理

第一类斯特林数递推式：$S_{n}^{k}=(n-1)S_{n-1}^{k}+S_{n-1}^{k-1}$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
#define N 50005
using namespace std;
const ll mod=1e9+7;
ll T,n,A,B,C[205][105],S[N][205];
void pre()
{
	ll i,j,k;
	for(i=0;i<205;i++)C[i][0]=1;
	for(i=1;i<205;i++)
	for(j=1;j<=i&&j<105;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	for(i=0;i<205;i++)S[i][i]=1;
	for(i=2;i<N;i++)
	for(j=1;j<i&&j<205;j++)S[i][j]=((i-1)*S[i-1][j]%mod+S[i-1][j-1])%mod;
}
int main()
{
	scanf("%lld",&T);pre();
	while(T--)
	{
		scanf("%lld%lld%lld",&n,&A,&B);
		if(A+B>n+1){puts("0");continue;}
		printf("%lld\n",C[A+B-2][A-1]*S[n-1][A+B-2]%mod);
	}
}