题解 P2532 【[AHOI2012]树屋阶梯】

发表一下自己关于这题是 **卡特兰数** 的观点。 我们用 $C_i$ 表示 $N = i$ 时的答案。 首先，显而易见，$C_0 = C_1 = 1$。 然后呢？我们画一张图:  图中所示是 $N = 5$ 的情况。 然后我们看到阶梯的右侧是若干拐角，我们标一下号：  很容易发现，这里有 $N$ 个拐角，而题目只允许我们放 $N$ 个矩形，也就是说，**每个矩形恰好覆盖一个拐角**。 为啥？如果一个矩形覆盖的拐角 $<1$，那必然有矩形覆盖的拐角 $>1$。那么比如你的矩形覆盖了两个拐角，你不妨画一画那个矩形长成什么样子，自然就明白是不可能的了。 我们把最左下角叫做 $o$ 点，它肯定要被一个矩形覆盖。  现在，我们枚举一下，覆盖 $o$ 的矩形覆盖了哪一个拐角。 * 覆盖 $1$：  那么右边就是一个 $N = 4$ 的子问题！方案数自然是 $C_4$，但也可以认为是 $C_0 \times C_4$。 * 覆盖 $2$：  上边就是 $N = 1$ 的子问题，右边就是 $N = 3$ 的子问题，根据乘法原理，方案数就是 $C_1 \times C_3$。 * 覆盖 $3$：  上边就是 $N = 2$ 的子问题，右边就是 $N = 2$ 的子问题，根据乘法原理，方案数就是 $C_2 \times C_2$。 * 覆盖 $4$：和覆盖 $2$ 同理。 * 覆盖 $5$：和覆盖 $1$ 同理。 于是，根据加法原理，我们就知道 $C_5 = C_0 \times C_4 + C_1 \times C_3 + C_2 \times C_2 + C_3 \times C_1 + C_4 \times C_0$。 更加的一般一点，我们就发现： $$C_N = \sum_{i = 0}^{N - 1} C_i \times C_{N - i - 1}$$ 这就是卡特拉数了，代码这里就不贴出了，求赞 QwQ。