显然结果为第 $n$ 个卡特兰数.

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int a[100005];
signed main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	int n;
	cin >> n;
	int ans = 1;
	for(int i = 1; i <= n; i++){
		ans = ans * (4 * i - 2) / (i + 1);
	}
    cout << ans;

	return 0;
}

时间复杂度：$O(n)$