HDU 4372 Count the Buildings [组合数学]

　　N个楼高度1~N，在最前面可以看到F栋楼，最后面可以看到B栋楼，求有多少种可能的排列。

　　对某几个数组成的集合，可以定义一个最大表示法，就是最大的数在最前面。F+B栋楼，去掉N之后，就是F+B-2个集合，选中其中的B-1个在前方按集合最大值升序排列，后方反之。然后对每个集合，不管怎样排列，看到的都是最大的那一个，可以想到是第一类stirling数，用N-1个数组成F+B-2个圈的排列数。

　　所以答案就是C(F+B-2,F-1)*S(N-1,F+B-2)。O(N^2)预处理，O(1)查询。

 1 #include <string.h>
 2 #include <stdio.h>
 3 #define MAXN 2005
 4 #define MOD 1000000007
 5 typedef long long LL;
 6 int n, f, b, cas;
 7 int c[MAXN][MAXN], s[MAXN][MAXN];
 8 void init(){
 9     for (int i = 0; i < MAXN; c[i++][0] = 1)
10         for (int j = 1; j <= i; j++)
11             c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD;
12     s[1][1] = 1;
13     for (int i = 2; i < MAXN; i++)
14         for (int j = 1; j <= i; j++)
15             s[i][j] = (s[i-1][j-1] + (LL)(i-1) * s[i-1][j]) % MOD;
16 }
17 int main(){
18     init();
19     scanf("%d", &cas);
20     while (cas--) {
21         scanf("%d%d%d", &n, &f, &b);
22         if(f+b-2>n-1)printf("%d\n",0);
23         else printf("%d\n",(LL)c[f+b-2][f-1] * s[n-1][f+b-2] % MOD);
24     }
25     return 0;
26 }