首页 > 代码库 > HDU 4372

HDU 4372

2024-07-26 19:17:58   212人阅读

想了很久，终于想到了。。。。

向后看到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


联系
我们