卡特兰数 get ！

· · 个人记录

卡特兰数递推公式：

首先，卡特兰数的第 n 项可以表示为 \dfrac{C^n_{2n}}{n+1}

那么就有了下图：

第二个公式就是：

catalan_i = \dfrac{catalan_{i-1}\times(4\times i-2)}{i+1}

入门：

传送门

直接上公式就切了啊。。。

signed main()
{
    cin >> n;
    catalan[0] = catalan[1] = 1;
    for(int i=2;i<=n;++i)
        catalan[i] = catalan[i-1]*(4*i-2)/(i+1);
    cout << catalan[n];
    return 0;
}