题目大意：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！
所以得出最终方程：
F(N)=(M+N)! * (M-N+1)/(M+1)
#include<iostream> #include<cstdio> using namespace std; #define base 10000 #define len 100 void multiply(int a[],int max,int b) { int i,array=0; for(i=max-1;i>=0;i--) { array+=b*a[i]; a[i]=array%base; array/=base; } } void divide(int a[],int max,int b) { int i,div=0; for(i=0;i<max;i++) { div=div*base+a[i]; a[i]=div/b; div%=b; } } int main() { int m,n,l,t=0; while(scanf("%d%d",&m,&n),m!=0) { int a[len]; memset(a,0,len*sizeof(int)); printf("Test #%d:\n",++t); if (m<n) printf("0\n"); else { int i; a[len-1]=1; for(int i=2; i<=m+n; i++) multiply(a,len,i); multiply(a,len,m-n+1); divide(a,len,m+1); for(i=0;i<len&&a[i]==0;i++); printf("%d",a[i++]); for(;i<len;i++) printf("%04d",a[i]); printf("\n"); } } return 0; }