排列组合(指数型母函数).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#define MAX 100
double cal[2][MAX];
double *pre,*now,*pt;
int n,m;
int a[11];
double fac[100];

int main()
{
	int i,j,k,sum;
	fac[0] = fac[1] = 1;
	for (i=2;i<=20;i++) {
		fac[i] = fac[i-1] * i;
	}
	while (scanf("%d %d",&n,&m)==2) {
		memset(cal,0,sizeof(cal));
		for (i=0;i<n;i++) {
			scanf("%d",&a[i]);
		}
		pre = cal[0];
		now = cal[1];
		pre[0] = 1;
		for (i=1;i<=a[0];i++) {
			pre[i] = 1.0 / fac[i];
		}
		for (i=1;i<n;i++) {
			for (j=0;j<MAX;j++) {
				if (pre[j] > 0) {
					for (k=0;k<=a[i];k++) {
						now[k+j] += pre[j] / fac[k];
					}
				}
			}
			pt = now;
			now = pre;
			pre = pt;
			memset(now,0,sizeof(cal[0]));
			pre[0] = 1;
		}
		printf("%.0lf\n",fac[m] * pre[m]);
	}
}