首页 > 代码库 > POJ 3088

POJ 3088

已知n,求n中取k(k<=n)个数组成的m(m<=n)个的集合的排列数.

于是,可以枚举选出k个数及枚举m个集合。这个很明显是二类斯特林数。而集合有序,则乘上m!

#include <iostream>#include <cstdio>#include <algorithm>#define LL __int64using namespace std;LL con_mul[15],Str[15][15];void initial(){	con_mul[0]=1;	for(LL i=1;i<=11;i++)	con_mul[i]=con_mul[i-1]*i;	for(LL i=0;i<=11;i++){		for(LL j=0;j<=i;j++){			if(i==j)			Str[i][j]=1;			else if(j==0&&i>=1){				Str[i][j]=0;			}			else{				Str[i][j]=j*Str[i-1][j]+Str[i-1][j-1];			}		//	cout<<Str[i][j]<<‘ ‘;		}	//	cout<<endl;	}}int main(){	initial();	int n,kase=0;	LL ans,Cnk,t;	scanf("%d",&n);	while(n--){		kase++;		ans=0;		scanf("%I64d",&t);		Cnk=t;		ans+=(Cnk*Str[1][1]);		for(LL i=2;i<=t;i++){			Cnk=Cnk*(t-i+1)/i;			for(LL k=1;k<=i;k++){				ans+=(Cnk*Str[i][k]*con_mul[k]);			}		}		printf("%d %I64d %I64d\n",kase,t,ans);	}	return 0;}

  

POJ 3088