难度： 绿

算法： 数学，Catalan 数，高精度

发现斜线上有 $n$ 个点，而一个矩形最多包含其中的一个，要放 $n$ 个矩形，于是每个矩形都包含一个这样的顶点。

然后左下角的点也要被包括。于是包括左下角点的矩形就把整个图形分为了两部分。发现这两部分就相当于 $n$ 更小的时候的情况。考虑 $dp$。记 $dp_i$ 为放置 $n$ 个矩形时的答案。那么有：

这不就是卡特兰数吗？

利用卡特兰数通项公式可以得到：

代码：（懒得写高精度了）

n=int(input());
a=1;
for i in range(2*n):
    a=a*(i+1);
for i in range(n+1):
    a=a//(i+1);
for i in range(n):
    a=a//(i+1);
print(a);