一列火车 n 节车厢，依次编号为 1,2,3,…,n。

每节车厢有两种运动方式，进栈与出栈，问 n 节车厢出栈的可能排列方式有多少种。

输入格式
输入一个整数 n，代表火车的车厢数。

输出格式
输出一个整数 s 表示 n 节车厢出栈的可能排列方式数量。

数据范围
1≤n≤60000

输入样例：

3

输出样例：

5

参考答案

#include <stdio.h>

const int N = 11311;
const int base = 1e9;  // 压 9 位
const int basebit = 9;

int n;
int sum[N];             // 存筛出的质数及其次数的结果
long long res[4500];    // 存答案，res[0] 存 res 的位数
int primes[N], cnt;     // 存筛的质数
bool st[120001];        // 筛质数用的 bool 数组

inline void init()      // 线性筛质数 + 求分解质因数的结果
{
    for (register int i = 2; i <= n << 1; i ++ )
    {
        if (!st[i])     // 如果 st[i] == false，说明该数 i 是质数
        {
            primes[ ++ cnt] = i; // 先把它存进 primes
            for (register int j = (n << 1) / i; j; j /= i) // 加上 (2n)! 含有 i 的数量。
                sum[cnt] += j;
            for (register int j = n / i; j; j /= i) // 减去 (n!)^2 含有 i 的数量。
                sum[cnt] -= j << 1; // (n!)^2 含有 i 的数量即两倍的 n! 所含有的 i 的数量，所以只用处理 n!，然后减去其所含数量两倍即可
            for (register int j = n + 1; j % i == 0; j /= i) // 减去 n + 1 含有 i 的数量
                sum[cnt] -- ;
        }
        for (register int j = 1; primes[j] <= (n << 1) / i; j ++ ) // 线性筛的板子
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break ;
        }
    }
}

inline int qmi(int a, int b) // 快速幂（其实并没有卵用。。大部分调用都会进到那个 if (b == 1) 里面去。。所以加了个特判，效率会更高一点）
{
    if (b == 1) return a;
    int res = 1;
    for (; b; a *= a, b >>= 1)
        if (b & 1) res *= a;
    return res;
}

inline void multi(int b)     // 将 res 乘 b
{
    register long long t = 0;
    for (register int i = 1; i <= res[0]; i ++ )
    {
        res[i] = res[i] * b + t;
        t = res[i] / base;
        res[i] %= base;
    }
    while (t) res[ ++ res[0]] = t % base, t /= base;
}

void print(int x, int i = basebit) // 快速输出 9 位
{
    if (!i) return ;
    print(x / 10, i - 1);
    putchar(x % 10 ^ 48);
}

int main()
{
    scanf("%d",&n);
    init();              // 初始化 primes + 初始化 sum
    res[0] = res[1] = 1; // 出初始化 res，res 的长度制为 1，res 的值制成 1
    for (register int i = 1; i <= cnt; i ++ ) // 枚举一遍分解出来的所有的质数
        if (sum[i]) multi(qmi(primes[i], sum[i]));
    printf("%lld", res[res[0]]);              // 第一位不用输出 9 位
    if (res[0] > 1)      // 如果 res 的位数大于一的话，那么输出后面的
        for (register int i = res[0] - 1; i; i -- )
            print(res[i]);
    return 0;
}