题意：
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 10000
double f[];
double dp[][];
int a[];
int main()
{
f[]=;
for(int i=;i<=;i++)
{
f[i]=f[i-]*i;
}
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=;i<=n;i++)
{
scanf("%d",a+i);
}
memset(dp,,sizeof(dp));
dp[][]=;
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
for(int k=;k<=a[i];k++)
{
if(k+j>n)
break;
dp[i%][j+k]+=dp[(i-)%][j]/f[k];
}
dp[(i-)%][j]=;
}
}
printf("%d\n",(int)(dp[n%][m]*f[m]+0.4));
}
return ;
}
还可以用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 10000
int dp[][];
int a[];
int c[][];
void ini()
{
c[][]=;
for(int i=;i<=;i++)
{
c[i][]=;
for(int j=;j<i;j++)
{
c[i][j]=c[i-][j]+c[i-][j-];
}
c[i][i]=;
}
}
int main()
{
int n,m;
ini();
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=;i<=n;i++)
{
scanf("%d",a+i);
}
memset(dp,,sizeof(dp));
dp[][]=;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
for(int k=;k<=a[i];k++)
{
if(j+k>m)
break;
dp[i][j+k]+=dp[i-][j]*c[j+k][k];
}
}
}
printf("%d\n",dp[n][m]);
}
return ;
}