配列組合せ[HDU 1521]

配列の組合せ
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 1736    Accepted Submission(s): 726
 
Problem Descriptionにはn種類のアイテムがあり、それぞれのアイテムの数がわかります.その中からm品を選ぶ配列数を要求する.例えば、2つのアイテムA、Bがあり、いずれも数が1で、その中から2つのアイテムを選ぶと、「AB」、「BA」の2種類が並んでいます.
 
 
 
Inputは入力データのセットごとに2行あり,1行目は2個数n,m(1<=m,n<=10)であり,物品数を表し,2行目はn個数であり,それぞれこのn個の物品の数を表す. 
 
Outputは、データのセットごとに配列数を出力します.(いずれの演算も2^31の範囲を超えない) 
 
Sample Input2 21 1 
 
Sample Output2 
 
Authorxhd 
 
Recommendxhd
 
A typical application of exponential generating function.The i-th good's generating function is (1+x/1!+x^2/2!+......+x^C[i]/C[i]!).In the product of the n functions,the coefficient of the item whose index of x is n multiplies n! is the finally answer.
 

#include<stdio.h>

#include<string.h>

double p[15],frac[15],tmp[15];

int c[15];

int n,m;

int main()

{

	int n,m,i,j,k;

	frac[0]=1;

	for (i=1;i<12;i++) frac[i]=frac[i-1]*i;

	while (scanf("%d%d",&n,&m)!=EOF)

	{

		for (i=1;i<=n;i++) scanf("%d",&c[i]);

		memset(p,0,sizeof(p));

		for (i=0;i<=c[1];i++) p[i]=1.0/frac[i];

		for (i=2;i<=n;i++)

		{

			memset(tmp,0,sizeof(tmp));

			for (j=0;j<=m;j++)

				for (k=0;k<=c[i];k++)

					tmp[j+k]+=p[j]*(1.0/frac[k]);

			for (j=0;j<=m;j++) p[j]=tmp[j];

		}

		printf("%.0lf
",p[m]*frac[m]);

	}

	return 0;

}