首页 > 代码库 > 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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。