算法
(组合计数,卡特兰数) $O(n^2)$
首先任何一种合法的入栈、出栈操作序列都可以得到一个不同的1~n的排列,因此可以得到的排列总数等于合法入栈、出栈操作序列的个数。
将入栈操作记作0,出栈操作记作1,那么任意一个合法的入栈、出栈操作序列都和AcWing 889. 满足条件的01序列中定义的合法01序列一一对应,因此本题的答案和上一题相同,都是第n个卡特兰数。
时间复杂度
在本题中我们使用公式 $C_n^m = C_{n-1}^m + C_{n-1}^{m-1}$ 来计算卡特兰数。时间复杂度是 $O(n^2)$。
C++ 代码
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 40;
LL c[N][N];
int main()
{
for (int i = 0; i < N; i ++ )
for (int j = 0; j <= i; j ++ )
if (!j) c[i][j] = 1;
else c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
int n;
cin >> n;
cout << c[n * 2][n] / (n + 1) << endl;
return 0;
}
在这里补一个y总的高精计算卡特兰数
https://www.acwing.com/activity/content/code/content/28166/
棒!
https://www.acwing.com/problem/content/131/也可以啊