Luogu 4609 - [FJOI2016]建筑师

题目要求等价于将 $n$ 个城市划分成 $a + b - 1$ 个城市群,每一个城市群有一个最高的城市,只能看见之。

对于一个大小为 $k$ 的城市群,有 $(k - 1)!$的方案数,等价于将他们组成一个圆排列的方案数。

由于高度为 $n$ 的城市自成一个城市群,于是我们将 $n - 1$ 个城市分成 $a + b - 2$ 个城市群,即:

同时,还要计算哪 $a - 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
30
31
32
33
#include <bits/stdc++.h>

#define MAXN 50005
#define MAXM 205

typedef long long lint;

using namespace std;

int t, n, a, b;
lint C[MAXM][MAXM], S[MAXN][MAXM];
const int M = 200, N = 50000, mod = 1e9 + 7;

void init() {
S[0][0] = C[0][0] = 1;
for (int i = 1; i <= M; ++i) {
C[i][0] = 1;
for (int j = 1; j <= i; ++j)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= M; ++j)
S[i][j] = (S[i - 1][j - 1] + S[i - 1][j] * (i - 1) % mod) % mod;
}

int main() {
init();
scanf("%d", &t);
while (t--) {
scanf("%d%d%d", &n, &a, &b);
printf("%lld\n", C[a + b - 2][a - 1] * S[n - 1][a + b - 2] % mod);
}
}