题意大概是,有一排高度在1~n之间各不同高的楼房,站在第一栋楼前看,可以看到f栋楼,站在最后一栋后看,可以看见b栋楼,问楼房可以多少种排列方法。
不管从前还是从后看,最高的那栋楼【即高度为n】是一定会被看见的。在前面看到的f-1栋的高度一定是递增的,同理在后面看的b-1栋楼的高度一定是递减的。
往前看时在两栋被看见的楼之间的高度一定比前一栋楼矮,它们之间的排列方式是全排列,同理在后面看的时候。
注意到,k-1个元素的全排列的种数就是k个元素的环排列。
于是问题可以转化为,在最高楼的两侧,有f-1个环和b-1个环的排列种数。
直接去掉最高的楼,组合数算出挑选f-1+b-1个可见楼的总方案数,再乘以第一类斯特林数s(n-1, f-1+b-1)。
#include <iostream> #include <stdlib.h> #include <stdio.h> #include <string.h> #include <algorithm> #include <math.h> using namespace std; typedef __int64 LL; const int mod = 1e9 + 7; const int maxn = 2005; int n, f, b, cas; int c[maxn][maxn], s[maxn][maxn]; void init() { for(int i = 0; i < maxn; c[i++][0] = 1) for(int j = 1; j <= i; j++) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod; s[1][1] = 1; for(int i = 2; i < maxn; i++) for(int j = 1; j <= i; j++) s[i][j] = (s[i - 1][j - 1] + (LL)(i - 1) * s[i - 1][j]) % mod; } int main() { init(); scanf("%d", &cas); while(cas--) { scanf("%d%d%d", &n, &f, &b); if(f + b - 2 > n - 1) printf("0\n"); else printf("%I64d\n", (LL)c[f + b - 2][f - 1] * s[n - 1][f + b - 2] % mod); } return 0; }