基于c++ 精确计算出栈序列数

栈序列的个数可以通过卡特兰数进行计算。卡特兰数是一种组合数，表示在不同的出栈顺序中，所有合法的入栈顺序的总数。

在一个栈中，假设有n个元素，可以进行的操作包括入栈和出栈。当一个元素进栈后，它只能在后续出栈操作中出栈。因此，对于任意一个合法的栈序列，最后一个出栈的元素一定是该序列中最后一个进栈的元素。设该元素为x，那么在x出栈之前，必须先将x之前进栈的所有元素依次出栈，否则x无法出栈。因此，在x出栈之前，x之前的所有元素必须按照某种顺序出栈，而x之后的元素则可以按任意顺序出栈。因此，对于一个栈序列，可以将x之前的元素看作一个子栈，x之后的元素看作一个子栈，因此问题可以转化为：给定一个长度为n的序列，将其划分为两个子序列，使得其中一个子序列的合法出栈顺序为另一个子序列的合法入栈顺序，求划分的方案数。

设f(n)表示n个元素的栈序列个数，则有：

f(n) = C(2n, n) / (n + 1)，其中C(n, m)表示从n个元素中选取m个元素的组合数。

以下是基于C语言的代码实现：

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    long long ans = 1; // 注意结果可能很大，需要使用long long类型
    for (int i = 1; i <= n; i++) {
        ans = ans * (n + i) / i; // 利用递推公式计算卡特兰数
    }
    printf("%lld\n", ans / (n + 1)); // 注意除以n+1
    return 0;
}