hdu1521（指数母函数）

排列组合

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 5209    Accepted Submission(s): 2287

Problem Description

有n种物品，并且知道每种物品的数量。要求从中选出m件物品的排列数。例如有两种物品A,B，并且数量都是1，从中选2件物品，则排列有"AB","BA"两种。

Input

每组输入数据有两行，第一行是二个数n,m(1<=m,n<=10)，表示物品数，第二行有n个数，分别表示这n件物品的数量。

Output

对应每组数据输出排列数。(任何运算不会超出2^31的范围)

Sample Input

2 2

1 1

Sample Output

2

解析：不能单纯的认为是一个简单的排列组合，不等于C(n,m)*A(m,m)，因为有可能重复。例如AAB，AAB

指数母函数自行了解

#include<bits/stdc++.h>
using namespace std;

#define e exp(1)
#define pi acos(-1)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define ll long long
#define ull unsigned long long
#define mem(a,b) memset(a,b,sizeof(a))
int gcd(int a,int b){return b?gcd(b,a%b):a;}

const int maxn=105;
int n,m,s[maxn];
double c1[maxn],c2[maxn],f[maxn];

void init()
{
	mem(c1,0);
	mem(c2,0);
}
int main()
{
	f[0]=1;
	for(int i=1; i<11; i++)f[i]=f[i-1]*i;
	while(~scanf("%d%d",&n,&m))
	{
		init();
		for(int i=0; i<n; i++)scanf("%d",&s[i]);
		
		for(int i=0; i<=s[0]; i++)c1[i]=1.0/f[i];
		for(int i=1; i<n; i++)
		{
			for(int j=0; j<=m; j++)
			{
				for(int k=0; k<=s[i]&&k+j<=m; k++)
				{
					c2[j+k]+=c1[j]*1.0/f[k];//注意与普通母函数不同 
				}
			}
			for(int j=0; j<=m; j++)
			{
				c1[j]=c2[j];
				c2[j]=0;
			}
		}
		printf("%.0f\n",c1[m]*f[m]); 
	}
	return 0;
}