Buy the Ticket

3 0
3 1
3 3
0 0

Test #1:
6
Test #2:
18
Test #3:
180

卡特兰数的应用、组合数学

m个人拿50，n个人拿100 ，可以用0代表50,1代表100；

1、首先当n>m时,显然sum=0;

2、m>=n时，序列总数为：m+n个位置中选出m个放上0，C(m+n, n) *m!*n!;
则合法数目=序列总数-不合法数目；
我们来考虑不合法序列的数目,
因为50元的共m个，当1的个数等于n=m+1是，无论怎样排列总是不合法！！即C(m+n,m+1)*m!*n!;
此序列即是不合法队列。

合法队列=C(m+n, n) *m!*n!-C(m+n,m+1)*m!*n!   化简得 (m+n)!*(m-n+1)/(m+1);

#include"stdio.h"
#include"string.h"
#define N 100
const int M=10000;
int main()
{
	int i,j,m,n,cnt=1;
	int a[N];
	while(scanf("%d%d",&m,&n),m||n)
	{
		printf("Test #%d:\n",cnt++);
		if(m<n)
		{
			printf("0\n");
			continue;
		}
		memset(a,0,sizeof(a));
		a[0]=1;
		for(i=1;i<=n+m;i++)
		{
			if(n!=0&&i==m+1)
				continue;
			for(j=0;j<N;j++)
			{
				a[j]*=i;
			}
			for(j=1;j<N;j++)
			{
				a[j]+=a[j-1]/M;
				a[j-1]%=M;
			}
		}
		if(n!=0)
		{
			for(i=0;i<N;i++)
				a[i]*=(m-n+1);
		}
		for(i=1;i<N;i++)
		{
			a[i]+=a[i-1]/M;
			a[i-1]%=M;
		}
		int flag=0;
		for(i=N-1;i>=0;i--)
		{
			if(flag)
				printf("%04d",a[i]);
			else if(a[i])
			{
				flag=1;
				printf("%d",a[i]);
			}
		}
		printf("\n");
	}
	return 0;
}

hdu 1133 Buy the Ticket,布布扣,bubuko.com

hdu 1133 Buy the Ticket

原文：http://blog.csdn.net/u011721440/article/details/24516977