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