Buy the Ticket(卡特兰数应用与大数)

hdu 1133

这个题其实是要学明白卡特兰数的推导过程，再加上大数存储就可以了。

在这个过程中幸好看到了一个大数模版，以后就用它了。

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define MAX 102
 
int factor[205][MAX];
int sim[201];
 
void multiply(int s[],int Max,int b) //高位在前低位在后，初始化[max]处为1，再运算。会自动增加位数
{
     int i,ans=0;
     for( i=Max;i>=0;i--)
     {
        ans+=s[i]*b;
        s[i]=ans%10000;
        ans/=10000;       
     }
}
 
void div(int s[],int b)
{
    int i,ans=0;
    for( i=0;i<=Max;i++)
    {
        ans=ans*10000+s[i];
        s[i]=ans/b;
        ans%=b;       
    }    
}
int getfactor(){  //得到(m+n)!
    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){
        if(n>m){
            printf("Test #%d:n",k++);
            printf("0n");                    
            continue;
        }
        memcpy(sim,factor[m+n],sizeof(int)*MAX);
        multiply(sim,m-n+1);
        div(sim,m+1);
        output(sim,k);
        k++;
    }
   
    return 0;
}