HDU 4372 Count the Buildings [第一类斯特林数]

有n(<=2000)栋楼排成一排，高度恰好是1至n且两两不同。现在从左侧看能看到f栋，从右边看能看到b栋，问有多少种可能方案。

T组数据， (T<=100000)

---

自己只想出了用DP搞

发现最高的楼一定能看到，分成了左右两个问题

f[i][j]表示i栋楼从左面可以看到j栋方案数，转移枚举最高楼左面有几栋楼，乘上个组合数和剩下的排列

问题是DP完了求ans需要O(n)枚举最高楼在哪........

然后发现好多人用了第一类sirtling数

考虑一栋被看到的楼，它会挡住它右面的几栋楼，这几栋楼可以任意排列都不会被看到

我们把这样作为一组，然后发现去掉最高的楼后左面需要f-1组，右面需要b-1组

一个组的最高元素必须在最左面，发现这样意味着是循环同构的(一种循环只有最高在最左合法)，就是第一类sirtling数啊

$ans={{f+b-2}\choose {f-1}}*s(n-1,f+b-2)$

然后本题G++迷之RE

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=,MOD=1e9+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,f,b;

int c[N][N],s[N][N];

void ini(int n){

    c[][]=;

    for(int i=;i<=n;i++){

        c[i][]=c[i][i]=;

        for(int j=;j<i;j++) c[i][j]=(c[i-][j]+c[i-][j-])%MOD;

    }

    s[][]=;

    for(int i=;i<=n;i++){

        s[i][i]=;

        for(int j=;j<i;j++) s[i][j]=(s[i-][j-]+(ll)s[i-][j]*(i-)%MOD)%MOD;

    }

}

int main(){

    freopen("in","r",stdin);

    int T=read();

    ini();

    while(T--){

        n=read();f=read();b=read();

        printf("%lld\n",(ll)c[f+b-][f-]*s[n-][f+b-]%MOD);

    }

}