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;
}

补充：软件开发 , C++ ,