HDU 1133(Buy the Ticket Catalan 数的另一种应用，非常重要！)

题目大意：M+N个人排队买票，票的单价是50￥，每个人只能买一张。 M个人拿50的去买，N个人拿100的去买，然后悲剧的是售票处开始的时候没有钱，所以如果拿100块买票人前面的拿50块买票的人小于或者等于用100块买票的人，这种排队方式就不合法，也就是不能顺利全部都买到票（因为没零钱找了）！

题目分析：

这是一个Catalan数的非常经典的应用，买票问题，首先我们用"0"表示用50块买票的人，用“1”表示用100块买票的人，然而假设m=4,n=3,的一个序列是：0110100显然，它不合法，然后我们把他稍微变化一下：把第一个不合法的“1”后面的所有数0位为1， 1位为0；这样我们得到了另一个序列：0111011，显然他也不是合法的，但是在这里我们关注的不是他合不合法！只是说明每个不合法的都有一个这样的序列跟他一一对应！

所以我们计算公式就是：合法的排列方式=所有排列方式-非法排列方式

我们这里非法排列方式的计算 就是：(- )*M!*N!，然而在这题，因为每个人都是不同的，所以还要乘以 M！*N！

所以得出最终方程：

F（N）=(-)*M！*N！  ；

然后再化简一下;

F(N)=(M+N)! * (M-N+1)/(M+1)

大数运算模拟，

分别有：

大数阶乘

大数乘小数

大数除小数。

#include<iostream>
#include<cstdio>
#include<cstring>
#define MAX 201
using namespace std;
int factor[205][MAX]={0};
int sim[201]={0};
int multiply(int s[],int Max,int b){//the static number can't be a canliang
	int ans=0,i;
	for(i=Max;i>=1;i--){
		ans+=s[i]*b;
		s[i]=ans%10000;
		ans=ans/10000;
	}
	return 0;
}
int div(int s[],int Max,int b){
	int ans=0,t,i;
	for(i=1;i<=Max;i++){
		t=ans*10000+s[i];
		s[i]=t/b;
		ans=t%b;
	}
	return 0;
}
int getfactor(){
	int i;
	factor[0][MAX-1]=factor[1][MAX-1]=1;
	for(i=2;i<=203;i++){
		memcpy(factor[i],factor[i-1],MAX*sizeof(int));//this has a falut that i have replace memcpy by strcpy!
		multiply(factor[i],MAX-1,i);
	}
	return 0;
}
int output(int *s,int k){
	int i=1;
	printf("Test #%d:\n",k);
	while(s[i]==0&&i<MAX)
		i++;
	printf("%d",s[i++]);
	for(;i<MAX;i++)
		printf("%04d",s[i]);
	printf("\n");
	return 0;
}
int main(){
	int m,n,i,k=1;
	getfactor();
	while(scanf("%d %d",&m,&n),m+n){
		memcpy(sim,factor[m+n],sizeof(int)*MAX);
		/*for(i=1;i<=MAX;i++){
			for(int j=1;j<MAX;j++)
				cout<<factor[i][j];
			cout<<endl;
		}*/
		if(n>m){
			printf("Test #%d:\n",k++);
			printf("0\n");
                        //别忘记了 判断这种情况，
                       //当初为了这个BUG找了好苦，5555....
			continue;
		}
		multiply(sim,MAX-1,m-n+1);
		div(sim,MAX-1,m+1);
		output(sim,k);
		k++;
	}
	return 0;
}