HDU4372CounttheBuildings（第一类斯特林数）

题目链接

n个房子 高度1–n 要你来重新排列这些房子 使得能够在某个房子处&＃xff0c;从左看去有f个房子 从右看去有b个房子 的方案数
显然当我们在高度为n的房子时&＃xff0c;左/右览都可以看完&＃xff0c;那么以n为衔接点 分为两组 左边一组(x) 右边一组(y) 且满足x&＃43;y&＃61;n-1 (n定下来了&＃xff0c;不考虑)
那么显然在n的两侧&＃xff0c;只要两侧最值与n相邻,其余楼层随便排列即可 于是相当于要计算 第一类Stirling数 (n-1,x-1&＃43;y-1) *C(x-1&＃43;y-1,y-1); C是组合数计算式

ll dp[2001][2001];
ll c[2001][2001];
inline void pre(ll n){for(ll i&＃61;1; i<&＃61;n; i&＃43;&＃43;) c[i][0]&＃61;1;dp[1][1]&＃61;c[1][1]&＃61;1;for(ll i&＃61;2; i<&＃61;n; i&＃43;&＃43;){for(ll j&＃61;1; j<&＃61;i; j&＃43;&＃43;){c[i][j]&＃61;(c[i-1][j-1]&＃43;c[i-1][j])%mods;dp[i][j]&＃61;(dp[i-1][j-1]&＃43;(i-1)*dp[i-1][j])%mods;}}
}int main(){
ll t&＃61;read();
ll p&＃61;2000;
pre(p);
while(t--){
ll n&＃61;read();
ll f&＃61;read();
ll b&＃61;read();
if(f&＃43;b-2<&＃61;2000){
printf("%lld\n",dp[n-1][f&＃43;b-2]*c[f&＃43;b-2][b-1]%mods);
}
else{printf("0\n");
}
}
return 0;
}