题目描述

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

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

输入格式

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

输出格式

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

数据范围

$1 \leq n \leq 60000$

输入样例：

3

输出样例：

5

算法

(暴力 卡特兰数 + 压位高精) $O(n^2)$

做这道题之前，建议先做一下 AcWing 129. 火车进栈 和 AcWing 889.满足条件的$01$序列 这两题。

看到数据范围，知道这题肯定是不能用暴力来做。
那么我们就需要先转化一下题目意思。

首先规定 $1$ 表示栈中进入一节车厢，$0$ 表示栈中弹出一节车厢，那么每种火车进出栈方案都能用一串 $01$ 序列来表示。
由于每节车厢都要进栈一次出栈一次，所以每种方案所对应的 $01$ 序列的长度都是 $2n$。
那么火车进出栈方案的总数量就可以看成是所有合法的 $01$ 串的个数。

那咋算是合法的嘞？
要有车厢出栈，那么栈中就必须要有车厢。
在 $01$ 序列中，就对应了在任意位置，其前面的 $1$ 的个数大于等于其前面 $0$ 的个数
所以这题就变成了 AcWing 889.满足条件的$01$序列

我们只需求卡特兰数即可。

但高精和卡时让这题恶心了很多。

首先我们要求高精的 $\displaystyle \frac{C _ {2n} ^ n}{n + 1}$，也就是高精的 $\displaystyle \frac{(2n)!}{(n!)(n!)(n + 1)}$
最快的办法是求出这玩意所有的质因数及其次数，然后求所有数乘积即可。
求出它所有的质数的方法可以参考 AcWing 197. 阶乘分解 这题的做法。
我这里是直接在筛质数的时候处理，更好写一些，且效率更高。
然后在乘所有数的乘积的时候，注意到每个数字的次数都不会太多，可以先求出 $primes[i] ^ {primes[i]的次数}\ \ $ 的结果，再乘到答案里面去，效率更高。

看y总视频里面调代码好辛苦，这里给出一份跑的超快的代码，最快一次 $315ms$ 跑完所有数据

C++ 代码

#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;
}