题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1023

 

该题就是求卡特兰数，只是处理的时候要用大数来处理，

使用递推公式：

h(n)=C(2n,n)/(n+1) (n=0,1,2,...)

= A(2n,n)/(n+1)!

 

改写我先求A(2n,n)

然后除以(n+1)!

1 #include 
     
       2 #include 
      
        3 #include 
       
         4  5 using namespace std; 6  7 #define N 250 8 int a[N]; 9 10 void init(int n)11 {12     memset(a,0,sizeof(a));13     a[0] = 1;14     int i = 0;15     int j = 0;16     int k1 = 1;17     for(i = 2*n; k1 <= n; i--,k1++)18       {19           int t = 0;20           int mul = 0;21           for(j = 0; j <= N; j++)22             {23                mul = a[j] *i + t;24                a[j] = mul % 10;25                t = mul / 10;26             }27       }28 29     for(i = 2; i <= n+1; i++)30         {31             int t1 = 0;32             int mul1 = 0;33             for(j = N; j >= 0;j--)34                 {35                     mul1 = mul1 *10 + a[j];36                     a[j] = mul1 / i;37                     mul1 %= i;38                 }39         }40 41   int k = N;42   while(k--)43    if(a[k])44      break;45     k += 1;46     while(k--)47       printf("%d",a[k]);48       printf("\n");49 }50 51 int main()52 {53     int n;54     while(scanf("%d",&n) != EOF)55      {56          if(n < 2)57            printf("%d\n",1);58         else59          init(n);60      }61     return 0;62 }