火车进站（卡特兰数）（HDU1023）

例题链接：HDU1023:https://vjudge.net/problem/HDU-1023
具体解体思路可以看Catalan数的基础介绍篇（虽然这个题也很基础）

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
int a[105][100];
void multiply(int a[],int b)
{
    int x=0;
    for (int i=99;i>=0;i--)
    {
        x=x+a[i]*b;
        a[i]=x%10000;
        x=x/10000;
    }
}
void divide(int a[],int b)
{
    int x=0;
    for (int i=0;i<=99;i++)
    {
        x = x*10000 + a[i];
        a[i]=x/b;
        x=x%b;
    }
}
int main()
{
    a[1][99]=1;
    for (int i=2;i<=100;i++) //打表
    {
        memcpy(a[i], a[i-1], sizeof(a[i-1]));
        multiply(a[i],4*i-2);
        divide(a[i],i+1);
    }
    int n;
    while(cin >> n)
    {
        int i;
        for (i=0;i<=99;i++)
        {
            if(a[n][i]==0) continue;
            else break;
        }
        cout << a[n][i];
        for (i=i+1;i<=99;i++)
        {
            printf("%04d",a[n][i]);
        }
        cout << endl;
    }
    return 0;
}