hdu-1130（卡特兰数+大数乘法，除法模板）

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

卡特兰数:https://blog.csdn.net/qq_33266889/article/details/53409553

参考文章：https://blog.csdn.net/sunshine_YG/article/details/47685737

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int base = 10000;
const int maxn = 100;
int a[maxn+20][maxn+20],n,i,j;
void Init()
{
    int tmp;
    a[1][1]=1;a[2][1]=2;a[3][1]=5;
    for(i=4;i<=100;i++)
    {
        for(j=1;j<100;j++)
        {
            a[i][j]+=a[i-1][j]*(4*i-2);
            a[i][j+1]+=a[i][j]/base;
            a[i][j]%=base;
        }
        for(j=100;j>=1;j--)
        {
            tmp=a[i][j]%(i+1);
            a[i][j-1]+=tmp*base;
            a[i][j]/=(i+1);
        }
    }
}
int main(void)
{
    Init();
    while(~scanf("%d",&n))
    {
        i=100;
        while(a[n][i]==0) i--;
        printf("%d",a[n][i--]);
        while(i>0) printf("%04d",a[n][i--]);
        printf("
");
    }
    return 0;
}