hdu 1023 Train Problem II

// 用h[n]表示n节火车的出站方法总数
// 那么分别考虑每一辆车最后出站
// 比如第一辆最后出站 则 有 h[0]*h[n-1]种出站方法
// 第二辆最后出站   则 有  h[1]*h[n-2]种出站方法
// ...
   
// 第i辆最后出站   则 有  h[i-1]*h[n-i]种出站方法 
// 卡特兰数 
// 递推公式 h[n]=h[n-1]*(4*n-2)/(n+1);
#include <iostream>
#include <string>
#include<sstream>
#include <cmath>
#include <map>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define  LL long long
#define Len 120
const int Base=10000;
void multiply(int a[],int len,int b)
{
    int i,m=0;
    for(i=0;i<len;i++)
    {
        m+=b*a[i];
        a[i]=m%Base;
        m/=Base;
    }
}
void divide(int a[],int len,int b)
{
    int i,div=0;
    for(i=len-1;i>=0;i--)
    {
        div=div*Base+a[i];
        a[i]=div/b;
        div%=b;
    }
}
int a[101][Len];
int main()
{

   memset(a[1],0,Len*sizeof(int));
   int i;
   for(i=2,a[1][0]=1;i<101;i++)
   {
      memcpy(a[i],a[i-1],Len*sizeof(int));
      multiply(a[i],Len,4*i-2);
      divide(a[i],Len,i+1);
   }
   int n;
   while(scanf("%d",&n)!=EOF)
   {
       for(i=Len-1;i>=0;i--)
        if(a[n][i]) break;
       printf("%d",a[n][i]);
       for(i--;i>=0;i--)
        printf("%04d",a[n][i]);
       printf("
");
   }
  return 0;
}