HDU4372 Count the Buildings

2012 Multi-University Training Contest 8
1003題

N座高樓，高度均不同且為1~N中的數，從前向後看能看到F個，從後向前看能看到B個，問有多少種可能的排列數。
0 < N, F, B <= 2000

組合數學。
ans(n, f, b) = C[f + b - 2][f - 1] * S[n - 1][f + b - 2];
C：組合數
    因為最高的樓層必然是N，我們只考慮兩邊能看到的樓層的數目f + b - 2。
    第二項f - 1和b - 1是等效的，代表一側能看到的樓層的數目減去最高的那個樓層，這樣所有能看到的樓層就被分配完了。
    C[n][m] = C[n-1][m-1] + C[n-1][m]
S：第一類Stirling數
    上面組合完成後，對於每一組，求它去掉最高樓層後的第一類Stirling數，每個圈選擇最高的作為可以看到的樓層。
    S[n][m] = S[n-1][m-1] + S[n-1][m] * (n - 1)
兩者相乘即為答案。

[cpp] 
#include <cstdio> 
#include <cstring> 
#include <algorithm> 
using namespace std; 
const int MAXN = 2010; 
const int MOD = 1000000007; 
 
int c[MAXN][MAXN]; 
int s[MAXN][MAXN]; 
bool vc[MAXN][MAXN]; 
bool vs[MAXN][MAXN]; 
 
int C(int n, int m) 
{ 
    if(vc[n][m]) 
    { 
        return c[n][m]; 
    } 
    if(m > (n >> 1)) 
    { 
        return C(n, n - m); 
    } 
    vc[n][m] = true; 
    if(m == 0) 
    { 
        return c[n][m] = 1; 
    } 
    if(m == 1) 
    { 
        return c[n][m] = n; 
    } 
    return c[n][m] = (C(n - 1, m - 1) + C(n - 1, m)) % MOD; 
} 
 
int S(int n, int m) 
{ 
    if(vs[n][m]) 
    { 
        return s[n][m]; 
    } 
    if(n < m || m == 0) 
    { 
        return 0; 
    } 
    vs[n][m] = true; 
    if(n == 1 && m == 1) 
    { 
        return s[n][m] = 1; 
    } 
    return s[n][m] = ( S(n-1, m-1) + ( (__int64)S(n-1, m) * (n - 1) ) % MOD ) % MOD; 
} 
 
int solve(int n, int f, int b) 
{ 
    if(f + b - 1 > n) 
    { 
        return 0; 
    } 
    return ( (__int64)C(f + b - 2, f - 1) * S(n - 1, f + b - 2) ) % MOD; 
} 
 
int main() 
{ 
    int n, f, b; 
    int caseNumber; 
    scanf("%d", &caseNumber); 
    while(caseNumber--) 
    { 
        scanf("%d%d%d", &n, &f, &b); 
        printf("%d\n", solve(n, f, b)); 
    } 
    return 0; 
}