首页 > 代码库 > hdu 4372 第一类stirling数的应用/。。。好题

hdu 4372 第一类stirling数的应用/。。。好题

 1 /**
 2 大意: 给定一系列楼房,都在一条水平线上,高度从1到n,从左侧看能看到f个, 从右侧看,能看到b个,问有多少种这样的序列。。
 3 思路: 因为肯定能看到最高的,,那我们先假定最高的楼房位置确定,那么在其左边还有f-1个能看见,在其右边还有b-1个,能看见。。所以可以这样将题目转化: 将除最高楼之外的n-1个楼,分成f-1+b-1 组,在最高楼左边f-1 组,在其右边b-1组,那么分成f-1+b-1 组  就是第一类Stirling数。s[n-1][f-1+b-1]。。左边f-1 组,在其右边b-1组,就是将这f-1+b-1 组,组合c(f-1+b-1,f-1)
 4 **/
 5 
 6 #include <iostream>
 7 
 8 using namespace std;
 9 const long long mod = 1000000007;
10 long long c[2010][2010];
11 long long s[2010][2010];
12 
13 void init(){
14     c[0][0] =1;
15     for(int i=1;i<=2000;i++){
16         c[i][0] = c[i][i] =1;
17         for(int j=1;j<i;j++){
18             c[i][j] = (c[i-1][j]+c[i-1][j-1])%mod;
19         }
20     }
21 
22     for(int i=1;i<=2000;i++){
23         s[i][0] =0;
24         s[i][i] =1;
25         for(int j=1;j<i;j++)
26             s[i][j] = (s[i-1][j-1]+(s[i-1][j]*(i-1))%mod)%mod;
27     }
28 
29 }
30 
31 int main()
32 {
33     init();
34     int t;
35     cin>>t;
36     while(t--){
37         int n,f,b;
38         cin>>n>>f>>b;
39         long long res =0;
40        if(f+b-1<=2000)
41             res = (s[n-1][f+b-2]*c[f+b-2][f-1])%mod;
42         else
43             res =0;
44         cout<<res<<endl;
45     }
46     return 0;
47 }