G21 第一类斯特林数

题目情境#

题目描述

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

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

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

输入格式

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

输出格式

对于每组数据输出一行答案 $\text{mod } 10^9+7$。

输入 #1

2
3 2 2
3 1 2

输出 #1

2
1

对于 $100 \%$ 的数据 ：$1 \leq n \leq 50000, \ 1 \leq A, B \leq 100, \ 1 \leq T \leq 200000$。

算法解析：#

第一类斯特林数 $s(n,k)$ 表示把 $n$ 个不同元素分成 $k$ 个非空圆排列的方案数。递推式：$s(n,k)=s(n-1,k-1)+(n-1)s(n-1,k)$——新元素单独成一个圆排列，或插入已有 $n-1$ 个元素的任意一个圆排列中（$n-1$ 种插入位置）。边界 $s(0,0)=1,\ s(n,0)=0\ (n>0)$。

打表找到规律后直接使用。

C++代码：#

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=50010, M=210, P=1e9+7;
long long 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])%P;
  for(int i=0; i<M; i++) C[i][0]=1;
  for(int i=1; i<M; i++)
    for(int j=1; j<=i; j++)
      C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;  
}
int main(){
  init();
  int T, n, a, b, ans;
  scanf("%d", &T);
  while(T--){
    scanf("%d%d%d", &n, &a, &b);
    ans=S[n-1][a+b-2]*C[a+b-2][a-1]%P;
    printf("%d\n", ans);
  }
}