POJ 3088

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

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

#include <iostream>
#include <cstdio>
#include <algorithm>
#define LL __int64
using 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
",kase,t,ans);
	}
	return 0;
}