首页 > 代码库 > hdu1521：排列组合---指数型母函数
hdu1521：排列组合---指数型母函数
题意：
n种元素，每种有 ni个，选出 m 个的排列有多少种
题解：
指数型母函数的裸题
x^n 项的系数为 an/n!....
代码如下：
#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>using namespace std;#define MAXN 10000double f[11];double dp[2][11];int a[11];int main(){ f[0]=1; for(int i=1;i<=10;i++) { f[i]=f[i-1]*i; } int n,m; while(scanf("%d%d",&n,&m)!=EOF) { for(int i=1;i<=n;i++) { scanf("%d",a+i); } memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=n;i++) { for(int j=0;j<=n;j++) { for(int k=0;k<=a[i];k++) { if(k+j>n) break; dp[i%2][j+k]+=dp[(i-1)%2][j]/f[k]; } dp[(i-1)%2][j]=0; } } printf("%d\n",(int)(dp[n%2][m]*f[m]+0.4)); } return 0;}
还可以用dp 做。。
dp[i][j]表示 前i种元素取了j个的种类数
转移的时候乘上组合数。具体见代码：
#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>using namespace std;#define MAXN 10000int dp[11][11];int a[11];int c[11][11];void ini(){ c[0][0]=1; for(int i=1;i<=10;i++) { c[i][0]=1; for(int j=1;j<i;j++) { c[i][j]=c[i-1][j]+c[i-1][j-1]; } c[i][i]=1; }}int main(){ int n,m; ini(); while(scanf("%d%d",&n,&m)!=EOF) { for(int i=1;i<=n;i++) { scanf("%d",a+i); } memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=n;i++) { for(int j=0;j<=m;j++) { for(int k=0;k<=a[i];k++) { if(j+k>m) break; dp[i][j+k]+=dp[i-1][j]*c[j+k][k]; } } } printf("%d\n",dp[n][m]); } return 0;}
hdu1521：排列组合---指数型母函数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。