洛谷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\) 。
根据卡特兰数的某常用公式，不难发现这是卡特兰数（？ \[ C_n =\sum_{i=1}^{n}C_{i-1}C_{n-i} \] 只不过这里换成了 \(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]))参考文献：
