洛谷 P1044 [NOIP2003 普及组] 栈 题解

洛谷 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;
}