洛谷P1044 栈

题目描述:

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

思路:

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

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

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

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

解释代码里有。

代码:

1
2
3
4
5
6
7
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))) # 直接计算卡特兰数