题目描述:

问一个栈的出栈顺序有几种，一道很经典的题目了

思路:

明显，这是一道卡特兰数的模板题，我们来看看如何使用卡特兰数的组合数公式。

预计算出阶乘，就可以用下面的公式来计算组合数了

$$ C^n_m=n!\div m! \div (n-m)!$$

由于python自带高精度，这道题用python就十分简单了

解释代码里有。

代码:

fact=[1] # fact用来存阶乘
def comb(n,i): # 计算组合数的函数
    return(fact[n]/fact[i]/fact[n-i])
for i in range(1,10000):
    fact.append(fact[i-1]*i) # 预计算阶乘
n=int(input()) # 输入n
print(int(comb(2*n,n)//(n+1))) # 直接计算卡特兰数