题目连接
题目概述
大概的题意是在一条街道上有(N)栋楼,按从1到(N)进行编号,已知这里每一栋楼的高度都不相同并且范围都在1到(N)之中,现在已知从第一栋楼前面向后看,可以看到(F)个,从最后一栋楼向前看,可以看到(B)栋楼,给出(N,F,B),计算符合条件的楼的排列的情况.
初始想法
很明显,一个从前向后看,另外一个从后向前看,那么此时最高的那栋楼(高度为N)的一定都能被看见,所以从第一栋楼到最高的那栋楼之间的楼的高度组成的一个序列中,一定存在一个长度为(F-1)的长度单调增的子序列,但是前半部分总体不一定呈现单调增;同样的,从最后一个向前看,一定存在着一个长度为(B-1)的楼高单调增的子序列.
进一步想法
对于前面这(F-1)它们是单调增的,但是中间可能有其它楼间隔,如果将按照这些楼对它们进行分组的话,可以得到(F-1)组,并且最高的一定位于最左面,组内剩下的(k-1)个元素进行全排列,有((k-1)!)中,所以这一组(k)个元素构成一个圆排列.同样的,后面部分也可以这样处理,于是每一组构成一个圆排列,总共有(F-1+B-1)组,从(N-1)个元素中选择(F-1+B-1)组构成圆排列,对应第一类斯特林数.在每一个圆排列中固定这组最大的元素,等价于有(F-1+B-1)个数,然后从这里面选择(F-1)个数,并按升序排列,有(C_{F-1+B-1}^{F-1})中选择.所以总的方法数是:$$C_{F-1+B-1}^{F-1}cdot s(N-1, F-1+B-1)$$.
注意
题目中不保证(F-1+B-1 < N)总是成立,所以对于不满足这个约束的要特别判断输出0,否则会WA.
其它
组合数计算用(C_n^m = C_{n-1}^{m-1}+C_n^{m-1})来递推计算,第一类斯特林数用
(s(0,0)=1,s(n,0)=0,s(n,m)=s(n,m-1)+(n-1)s(n-1,m))来计算,可以提前打表计算好结果.
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 2005;
const int M = 1e9+7;
using ull = unsigned long long;
ull s[N][N];
ull c[N][N];
void calculate(){
s[0][0] = c[0][0] = 1;
for( int i = 1; i < N; ++i){
c[i][0] = 1;
for( int j = 1; j <= i; ++j){
s[i][j] = ((s[i-1][j-1] % M)+ ((i-1)*s[i-1][j] % M)) % M;
c[i][j] = (c[i - 1][j - 1] % M + c[i - 1][j] % M) % M;
}
}
}
int main(int argc, const char** argv) {
calculate();
int t;
scanf("%d", &t);
while(t--) {
int n, b, f;
scanf("%d%d%d", &n, &f, &b);
ull ans = 0;
if (f - 1 + b - 1 < n)
ans = ((c[b-1+f-1][f-1] % M) * (s[n-1][b-1+f-1] % M)) % M;
printf("%lld
", ans);
}
return 0;
}