【hdoj_1133】Buy the Ticket(卡特兰数+大数)

题目：http://acm.hdu.edu.cn/showPRoblem.php?pid=1133

题目的意思是，m个人只有50元钱，n个人只有100元整钱，票价50元/人.现在售票厅没钱，只有50元钱的人可以不用找钱顺利买票，而拿着100元整钱的人只有在前面有50元的情况下才能买票，因为只有这样，才能找零50元.所有的人能否买票和排队的方式有一定关系，问使得所有的人能够顺利买票的排队方式有多少种？

上述问题可以抽象为下面的数学模型，数学模型及求解过程如下图：

本题中每个人是不一样的，所以本题的最终结果：排列的总数应该为U*n!*m!，即：

下面本题的目标就是按照下面思路编程求解：

1.若m<n，则结果为0

2.若m>=n，则结果就是U*n!*m!.

题目m,n<=100，100！是一个很大的数，已有的数据类型无法存储，可以用数组存储，模拟【乘法】和【除法】.

【乘法】的过程见：http://blog.csdn.net/ten_sory/article/details/60476570

【除法】较复杂，这里可以【避免除法】.注意分母只有(m+1)，当n>=1的时候，(m+n)!包含(m+1)一项，直接在计算这个阶乘的时候，不计算这一项即可.当n=0的时候，本题的结果为m!.

C++代码如下：

#include<iostream>#include<string.h>using namespace std;void Multiply(int a[],int z)//大数a[]和小数z相乘，结果存储在a[]中{	int maxn = 2000;	int c = 0;	for(int j=maxn-1;j>=0;j--)//用z乘以a[]的每一位	{		int x = a[j] * z + c;		a[j] = x % 10;		c = x / 10;	}}int main(){	int m,n,num=0;	while(1)	{		cin >> m >> n;		if(!m && !n)			break;		cout << "Test #" << ++num << ":" << endl;		if(m<n)//m<n，没有符号条件的排列		{			cout << 0 << endl;			continue;		}		const int maxn = 2000;		int a[maxn],i,j;		memset(a,0,sizeof(a));		a[maxn-1] = 1;		if(n==0)//此时全是拿50元的人，直接输出m!的结果			for(i=2;i<=m+n;i++)//计算m!				Multiply(a,i);		else if(n>=1)//此时按照公式计算，避开除法		{			for(i=2;i<=m+n;i++)				if(i!=m+1)//如果，某一项恰好是分母(m+1),则不乘以这一项					Multiply(a,i);			Multiply(a,m-n+1);//根据公式，最后还要乘以(m-n+1)一项		}		for(i=0;i<maxn;i++)			if(a[i])//从i开始，非零				break;		for(j=i;j<maxn;j++)//输出			cout << a[j];		cout << endl;	}	return 0;}
上述代码，提交可以通过.
小结：
1.关于【卡特兰数】
    当m=n时，U的值就是n-卡特兰数，如下图：
更多关于卡特兰数的性质和应用，参看：http://blog.csdn.net/zhangmh93425/article/details/44677891
2.避开除法
    本题有一个小技巧，就是避开了除法，因为当n>=1的时候，分子(m+n)!中一定有一项为(m+1)，避开这一项，相当于先乘以这一项，再除以这一项.如此避开了麻烦的除法，但是要注意，当n=0的时候，(m+n)!中没有(m+1)这一项，则需要另作处理.