首页 > 代码库 > HDU 4372
HDU 4372
想了很久，终于想到了。。。。
向后看到F，向前看到B，假如把N-1个楼分成F+B个组，则把每个组最高的楼作为看到的楼，那么，其实在确定每一组的最高楼时，左边或右边的最高楼的顺序已经确定了。由于是排列数，联想到第一类斯特灵数，即可以顺利解决。那么，分成F+B个组后，选出B个组放在右边（最高楼的右边）即可。
注意在求组合数时，不要用逆元，可以使用递推公式
C(N,K)=C(n-1,k)+C(n-1,k-1);
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define LL __int64#define MOD 1000000007#define N 2000using namespace std;LL str[N+5][N+5];LL cnk[N+5][N+5];void initial(){ LL x,y; for(LL i=0;i<=N;i++){ for(LL j=0;j<=i;j++){ if(j==0) cnk[i][j]=1; else if(i==j) cnk[i][j]=1; else{ // cnk[i][j]=(cnk[i][j-1]*(i-j+1))%MOD; // exgcd(j,MOD,x,y); // cnk[i][j]=((cnk[i][j]*x)%MOD+MOD)%MOD; cnk[i][j]=(cnk[i-1][j-1]+cnk[i-1][j])%MOD; } if(i==j) str[i][j]=1; else if(j==0) str[i][j]=0; else{ str[i][j]=((str[i-1][j]*(i-1))%MOD+str[i-1][j-1])%MOD; } } }}int main(){ initial(); int T; LL n,f,b,ans; scanf("%d",&T); while(T--){ scanf("%I64d%I64d%I64d",&n,&f,&b); ans=(str[n-1][f+b-2]*cnk[f+b-2][b-1])%MOD; printf("%I64d\n",ans); } return 0;}
HDU 4372
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。