卡特兰数

卡特兰数的公式为$h (n) =C(2n,n) \div (n+1)!$

展开来就是$h (n) =2n! \div (n+1)! \div n!$　

本题的思路

根据公式如果直接来算$2n!$，$n$最大为$18$，开$long$ $long$也会爆，那么不妨在计算过程中进行一些优化。
首先被除数$2n!$和$n!$都有$n!$，那么可以直接不算。 然后部分代码为：

for(int i=n+2;i<=2*n;i++)
	sum*=i
for(int i=2;i<=n;i++)
   sum/=i;

这样还是不能$AC$，那么怎么优化呢？
我们不妨想当此循环$i$为$2$的倍数时，那么在之后除以 $(n+1)!$ 时还会除以 $i\div2$ 的值，那么这种$i$ 就干脆只乘以 $2$，那么就极大减小了$sum$ 所记录的值的防止爆空间。根据此思路就完成了AC代码

for(int i=n+2;i<=2*n;i++)
    {
    	if(i%2==0)
    		sum*=2;
    	else
    		sum*=i;
	}
    	
    for(int i=2;i<=n;i++)
    	if(i*2<n+2)
    		sum/=i;

防止直接抄题解就只有部分代码。