P4609 [FJOI2016]建筑师
将 $n$ 作为分界线，将一个建筑到 $n$ 中递减的建筑作为一个集合，一个极大集合称作一个部分，则左边共有 $A - 1$ 个部分，右边共有 $B - 1$ 。将剩下的 $n - 1$ 个数划分到 $A + B - 2$ 个圆排列。划分了圆排列后，每个部分的一个端点是确定了的，因此可以代表答案中的排列。
查看代码
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
| #include <cstdio>
using namespace std;
typedef long long LL;
const int N = 5e4 + 10, M = 210, mod = 1e9 + 7;
LL s[N][M], c[M][M];
void init()
{
s[0][0] = 1;
for (int i = 1; i < N; i++)
for (int j = 1; j < M; j++)
s[i][j] = (s[i - 1][j - 1] + (i - 1) * s[i - 1][j]) % mod;
for (int i = 0; i < M; i++)
for (int j = 0; j <= i; j++)
if (!j)
c[i][j] = 1;
else
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
int main()
{
init();
int T;
scanf("%d", &T);
for (int n, A, B; T; T--)
{
scanf("%d%d%d", &n, &A, &B);
printf("%lld\n", s[n - 1][A + B - 2] * c[A + B - 2][A - 1] % mod);
}
return 0;
}
|