HOJ 1130 How Many Trees?（卡特兰数，大数）

卡特兰数，大数
本题要点：
1、大数求前100项的卡特兰数，打表即可。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 101;
int n;struct bign
{
    int d[1000];int len;bign(){
    memset(d, 0, sizeof d);len = 0;}
}c[MaxN];bign multi(bign a, int b)
{
    bign c;int carry = 0;for(int i = 0; i < a.len; ++i){
    int tmp = a.d[i] * b + carry;c.d[c.len++] = tmp % 10;carry = tmp / 10;}while(carry != 0){
    c.d[c.len++] = carry % 10;carry /= 10;}while(c.len - 1 >= 1 && c.d[c.len - 1] == 0){
    c.len--;}return c;
}bign divide(bign a, int b, int & r)
{
    bign c;c.len = a.len;for(int i = a.len - 1; i >= 0; --i){
    r = r * 10 + a.d[i];if(r < b){
    c.d[i] = 0;}else{
    c.d[i] = r / b;r = r % b;}}while(c.len - 1 >= 1 && c.d[c.len - 1] == 0){
    c.len--;}return c;
}void init()
{
    int r = 0;c[1].d[0] = 1, c[1].len = 1;for(int i = 2; i < MaxN; ++i){
    c[i] = multi(c[i - 1], 4 * i - 2);c[i] = divide(c[i], i + 1, r);}
}void printBign(bign a)
{
    for(int i = a.len - 1; i >= 0; --i){
    printf("%d", a.d[i]);}printf("\n");
}int main()
{
    init();while(scanf("%d", &n) != EOF){
    printBign(c[n]);}return 0;
}/* 1 2 3 *//* 1 2 5 */