洛谷 P1044 [NOIP2003 普及组] 栈 题解
Sol
本题通过分析可得：
假设现在进行 \(12\) 次操作，我们把 push 认为是在地图上向右走，pop 向上走，那么其中一个合法的步骤可以是（\(p1\) 代表 push，\(p2\) 代表 pop)：\(p1, p1, p2, p1, p2, p2, p1, p1, p2, p2, p1, p2\)。
而且我们发现，他最终会走到 \((n, n)\) 的位置，且如果这个序列是一个合法序列（pushpop 串的任意前缀 \(\text{push}\) 的个数 \(\ge\) \(\text{pop}\) 的个数）它能在走的过程中保证会在 \((0, 0)\)，\((n, n)\)，\((n, 0)\) 这三个点围成的三角形内走动。
我们可以推出结果就是能走到 \((n, n)\) 的总数 \(-\) 非法个数，也就是 \(C^n_{2n} \times C^{n - 1}_{2n}\)。
\(C^{n}_{2n}\) 表示走 \(2n\) 步然后走到点 \((n, n)\)，共选取了 \(n\) 步往右走。
\(C^{n - 1}_{2n}\) 表示走 \(2n\) 步然后走到点 \((n - 1, n + 1)\)，共选取了 \(n - 1\) 步往右走。
接下来就可以化简了。
\(C^{n}_{2n} - C^{n - 1}_{2n}\)
\(= \dfrac{(2n)!}{(n!)^{2}} - \dfrac{(2n)!}{(n-1)!\ (n+1)!}\)
\(= \dfrac{(2n)!\ (n+1)-n(2n)}{(n+1)!\ n!}\)
\(= \dfrac{1}{n+1} \times \dfrac{(2n)!}{(n!)^{2}}\)
\(= \dfrac{C^{n}_{2n}}{n+1}\)
我们还可以推出：
\(C^{m}_{n} = C^{m-1}_{n-1} + C^{m}_{n-1}\)
那么代码就一呼而出了。
Code
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <stack>
using namespace std;
using ll = long long;
const int kMaxN = 110, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;
int n, f[kMaxN];
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
f[0] = 1, f[1] = 1;
for (int i = 2; i <= n; ++ i) {
for (int j = 0; j < i; ++ j) {
f[i] += f[j] * f[i - j - 1];
}
}
cout << f[n] << '\n';
return 0;
}