思路

这道题就是求卡特兰数($h(n),h(0)=h(1)=1$)，有三个公式：

1. 如果 $2 \le n$，则有 $h(n)=\sum_{i = 1}^{n-1} h(i)\times h(n-1-i)$。
2. $h(n+1)=h(n) \times \frac{2 \times (2n+1)}{n+2}$。
3. $h(n)=\frac{C^n_{2n}}{n+1}$。

code

#include<bits/stdc++.h>
using namespace std;
long long catalan(int x){
	if(x<=1)    return 1;
	return catalan(x-1)*2*(2*x-1)/(x+1);
}
int main(){
	int x;
	cin>>x;
	cout<<catalan(x);
	return 0;
}