洛谷P2532 [AHOI2012]树屋阶梯 题解
题目链接：P2532 [AHOI2012]树屋阶梯
题意：
有点搞笑的是，我刚刚写的 浅谈卡特兰数 （Catalan数） 恰好提到了这个。
所以它就是卡特兰数。当然观察样例手推也可以发现，1,1,2,5,14嘛。
当然这个题也是有理论依据的。
考虑证明它是一个 Catalan number。先去搬几张图（逃
设 $f_i$ 表示 $i$ 层高的阶梯的方案数，边界：$f_0=1,f_1=1$
考虑 $n=5$ 的情况，下图中红色的部分表示我们将要填充的块
可以发现它的方案数为 $f_0 \times f_{4}$ 。
考虑填充第二块
可以发现它的方案数为 $f_1 \times f_3$ 。
还没看出来吗？那再来一个。
可以发现它的方案数为 $f_2 \times f_2$ 。
根据卡特兰数的某常用公式，不难发现这是卡特兰数（？
只不过这里换成了 $f$ 。然后我们就做完这题了
代码：（又是高精度。。）
n = int(input());
if(n == 0 or n == 1): print(1); exit(0);
fac = [0 for i in range(2*n+5)]; fac[0]=1;
for i in range(1, 2*n+1): fac[i] = fac[i-1] * i;
print(fac[2*n] // (fac[n] * fac[n+1]))参考文献：
