题目描述
小 Z 是一个很有名的建筑师，有一天他接到了一个很奇怪的任务：在数轴上建 n 个建筑，每个建筑的高度是 1 到 n 之间的一个整数。
小 Z 有很严重的强迫症，他不喜欢有两个建筑的高度相同。另外小 Z 觉得如果从最左边（所有建筑都在右边）看能看到 A 个建筑，从最右边（所有建筑都在左边）看能看到 B 个建筑，这样的建筑群有着独特的美感。现在，小 Z 想知道满足上述所有条件的建筑方案有多少种？
如果建筑 i 的左(右)边没有任何建造比它高，则建筑 i 可以从左(右)边看到。两种方案不同，当且仅当存在某个建筑在两种方案下的高度不同。
输入格式
第一行一个整数 T，代表 T 组数据。 接下来 T 行，每行三个整数 n,A,B。
输出格式
对于每组数据输出一行答案 mod 1e9+7。
输入输出样例
输入 #1
2
3 2 2
3 1 2
输出 #1
2
1
说明/提示
对于 100% 的数据 ：1≤n≤50000, 1≤A,B≤100, 1≤T≤2000001。
这也出到我考试题里了，看到后一脸懵，题都没看懂（因为是简化题面），爆0了（我吐了）
这道题正解是组合数\(+\)第一类斯特林数。
我们如果要有A个前缀最大值，B个后缀最大值，我们可以把\(n\)个数分为\(A + B – 1\)段：高度为\(n\)的为一段，其余的是一个高的挡住一群矮的为一段，大概是这样的：
那么问题可以转化为：将\(n – 1\)个数分为\(A + B – 2\)段，并且每一段不能为空，这不就是第一类斯特林数吗？
最后再考虑每一段在最高的那段左边还是右边就好了，最高的那段左边应该有\(A – 1\)段，右边应该有\(B – 1\)段，所以再乘上个\(C_{A +B – 2} ^ {A – 1}\)就好了。
#include <iostream>
#include <cstdio>
#include <cctype>using namespace std;inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}const int N = 3005, M = 3005, mod = 998244353;
int n, a, b;
int jc[N], inv[N], c[M][M], s[N][M];void make_C() {
jc[0] = jc[1] = inv[0] = inv[1] = 1;
for(int i = 2;i <= M - 5; i++) jc[i] = 1ll * jc[i - 1] * i % mod;
for(int i = 2;i <= M - 5; i++) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
for(int i = 2;i <= M - 5; i++) inv[i] = 1ll * inv[i - 1] * inv[i] % mod;
for(int i = 0;i <= M - 5; i++) c[i][0] = 1;
for(int i = 1;i <= M - 5; i++) {
for(int j = 1;j <= M - 5; j++) {
if(i >= j) c[i][j] = 1ll * jc[i] * inv[j] % mod * inv[i - j] % mod;
}
}
s[0][0] = s[1][1] = 1;
for(int i = 2;i <= N - 5; i++) s[i][1] = 1ll * s[i - 1][1] * (i - 1) % mod;
for(int i = 2;i <= N - 5; i++) {
for(int j = 2;j <= M - 5; j++) {
if(i >= j) s[i][j] = (s[i - 1][j - 1] + 1ll * s[i - 1][j] * (i - 1) % mod) % mod;
}
}
}void init() {
scanf("%d %d %d", &n, &a, &b);
}void work() {
printf("%lld\n", 1ll * s[n - 1][a + b - 2] * c[a + b - 2][a - 1] % mod);
}int main() { // freopen("onesentence.in","r",stdin); freopen("onesentence.out","w",stdout); make_C();
init(); work(); // fclose(stdin); fclose(stdout);
return 0;
}
