摘要
Title: 130. 火车进出栈问题
Tag: 组合数、卡特兰数、阶乘
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

130. 火车进出栈问题

• 题意

  一列火车 n 节车厢，依次编号为 1,2,3,…,n。
  每节车厢有两种运动方式，进栈与出栈，问 n 节车厢出栈的可能排列方式有多少种

• 思路

  卡特兰数板子题

  ps: 用python的math库中自带的阶乘，在处理大数据上，比手写阶乘要快10倍不止

  前提是：不用取模！

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-03-12 16:50:02
  FilePath: \ACM\Acwing\889.py
  LastEditTime: 2022-03-12 16:50:03
  '''
  from math import factorial as fact
  
  n = int(input())
  a = fact(2 * n)
  b = fact(n)
  
  print(a // b // b // (n + 1))