P1044 [NOIP2003 普及组] 栈——卡特兰数

传送门：

P1044 [NOIP2003 普及组] 栈 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1044

公式一：递推式(注意开 long long ，然后 先乘完再除，防止下取整）

typedef long long ll;
ll K[20];
int main() {int n;cin >> n;K[0] = 1;for (int i = 1; i <= n; i++) {K[i] = K[i - 1]*(4 * i - 2) / (i + 1) ;}cout << K[n];
}

公式二：递归式子：

typedef long long ll;ll k[20];
int main() {int n;cin >> n;k[0] = 1;for (int i = 1; i <= n; i++) {for (int j = 0; j < i; j++) {k[i] += k[j] * k[i - j - 1];}}cout << k[n];
}

 公式三：通项公式

typedef long long ll;
ll frc[50][50];
int main() {int n;cin >> n;for (int i = 0; i <= 2*n; i++) {frc[i][0] = frc[i][i] = 1;for (int j = 1; j <= i; j++) {frc[i][j] = frc[i - 1][j - 1] + frc[i - 1][j];}}cout << frc[2 * n][n] / (n + 1);
}