题解 P1044 【栈】

· · 题解

从题目以及众多题解，我们可以知道这道题是一道卡特兰数，而卡特兰数的最终算数表达式子为： \frac{(2n)!}{(n+1)!(n)!}。

证明过程：

我们已经知道，栈有两种操作，入栈和出栈。对此，我们可以建立一个坐标系。

像这样:

我们可以把：

黄色的线作为入栈操作,由 (x,y) 变成 (x+1,y+1)。

绿色的线作为出栈操作,由 (x,y) 变成 (x+1,y-1)。

这样，我们就可以把问题转化为从 (0,0) 到 (2n,0)，有多少种合法的方案数。

我们先来考虑这样一个问题，因为我每一次操作都可以让 x+1,那么我总共要进行 2n 次操作，考虑到最后的栈要为空，所以入栈次数=出栈次数= n，所以方案数为 C_{2n}^n。

但是！！！ 我们这样，会出现非法的情况，也就是线越过x轴的情况（栈已经空了，但是还在弹出元素），如图:

对于这种情况，我们可以设 k 为第一次与 y=-1 这条直线的交点，然后把交点以后的点都关于 y=-1 对称（即，交换操作 1 和操作 2 ）。

因为我们现在的终点变成了 (2n,-2)，所以我们的入栈次数肯定等于出栈次数 -2。因为入栈次数加出栈次数等于 2n,所以入栈为 n-1 次，出栈 n+1 次，则有不合法的总方案数为 C_{2n}^{n-1}，所以最终结果为 C_{2n}^{n}-C_{2n}^{n-1}。

根据组合数的定义：

化简可以得到最终答案为 \frac{(2n)!}{(n+1)!(n)!}，证毕。

Code:

n=int(input())
m=2*n
a=1
for i in range(1,m+1):#计算(2n)!
    a=a*i
b=1
for i in range(1,n+2):#计算(n+1)!
    b=b*i
c=1
for i in range(1,n+1):#计算n！
    c=c*i
ans=int(a/(b*c))
print(ans)