首页 > 代码库 > HDU1521 排列组合 (指数型母函数)
HDU1521 排列组合 (指数型母函数)
题意:n,m,有n种物品每个物品有a[i]个,要求从中选出m件物品的排列数。
指数型母函数,g=a0+a1/1!*x+a2/2!*x^2+...+ak/k!*x^k...
指数型母函数详解#include <iostream> #include <stdio.h> #include <string.h> #include<string> #include<math.h> #include<queue> #include<stack> #include <algorithm> #include<vector> #include<set> using namespace std; #define M 100 #define inf 0x3fffffff #define ll __int64 const int mod=123456789; const int INF=1e9; const int maxn=100005; int fac[15]; int n,m; int num[15]; double c1[15],c2[15]; void init() { memset(c1,0,sizeof(c1)); memset(c2,0,sizeof(c2)); fac[0]=1; for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i; } int main() { while(~scanf("%d%d",&n,&m)) { for(int i=0;i<n;i++) { scanf("%d",&num[i]); } init(); for(int i=0;i<=num[0];i++) { c2[i]=1.0/fac[i]; } for(int i=1;i<n;i++) { for(int j=0;j<=m;j++) { for(int k=0;k+j<=m&&k<=num[i];k++) { c1[j+k]+=c2[j]/fac[k]; } } for(int j=0;j<=m;j++) { c2[j]=c1[j]; c1[j]=0; } } printf("%.0lf\n",c2[m]*fac[m]); } return 0; }
HDU1521 排列组合 (指数型母函数)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。