[0x11] 130.火车进站问题

题意

link（more：129.，P1044）

简化题意：给定严格从 \(1\thicksim n\) 这 \(n(n\leqslant 6\times10^4)\) 个整数，规定每个数都要进出栈各一次，求所有可能的出栈序列的数量。

这题有多种做法（爆搜，递推，dp，数学），最主要是 \(n\) 的范围，刚好会把像递推和 dp 这样的 \(O(n^2)\) 的次优化算法卡掉。

显然复杂度就要求是线性的，如此，可以使用组合数学中的 卡特兰数Catalan（link）。

太冷了，12.4补。