进出栈序列问题

题目描述

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

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

样例

输入样例：
3
输出样例：
5

算法

(卡特兰数 + 高精度乘法（压位） + 计算组合数)

卡特兰数：

$结论：卡特兰数 = \frac{ C_{2n} ^{n}}{n +1}$

火车进出站排列方式个数是经典的卡特兰数

可以把火车进出栈的操作抽象一下

$n$ 辆火车总共会进栈 $n$ 次，出栈 $n$ 次

总共是 $2n$ 次操作

并且任意一次出栈操作合法的前提是栈中有火车

我们将每一个完整的合法的操作序列抽象成

在一个平面直角坐标系上

从点 $(0,0)$ 走到 $(n,n)$ 的路径

入栈操作对应到沿着平行于 $x$ 轴的直线向右走一个单位距离

出栈操作对应到沿着平行于 $y$ 轴的直线向上走一个单位距离

并且任意时刻向右走的距离都大于等于向上走的距离(因为原问题中栈中必须有火车才能出栈)

总共会向右走n步，向上走n步

所以路径和原问题是一一对应的

图片说明

图中的红色线条表示向右走的路线，绿色线条表示向上走的路线，绿点表示终点

图中的红-绿路径是一个合法的路径

从 $(0,0)$ 走到终点 $(n,n)$ 的方案总共有 $C_{2n}^{n}$ 种（2n个操作从中选n个往上走或者选n个往右走）

而合法的路径就是将总方案数减去不合法的方案数

接着我们就求不合法的方案数

我们发现任何一条合法的路径都不会与直线y = x + 1有任何交点

即不会与图中的浅蓝色的直线有交点

不合法的路径如下图
图片说明

黄色线条的路径与直线 $y = x + 1$ 有四个交点（红点）所以是不合法的路径

找到不合法路径与浅蓝色直线的第一个交点

并将这个点后面的路线按照浅蓝色直线轴对称

得到下图的紫色部分

图片说明

图中的紫色路径与前面的黄色路径组成的新路径是一条从 $(0,0)$ 到 $(n - 1,n + 1)$ 的路径

我们发现任意一条不合法路径都可以通过相同的构造得到一条一条从 $(0,0)$ 到 $(n - 1,n + 1)$ 的路径

而合法的路径则不能

所以不合法的路径个数就是 $C_{2n}^{n - 1} = C_{2n}^{n +1}$

所以： $卡特兰数 \ = \ C_{2n}^{n} - C_{2n}^{n - 1}$
$= \frac{2n * ... *(n + 1)}{n!}\ - \ \frac{2n * ... * n}{(n + 1)!}$
$= \frac{2n * ... *(n + 1) * (n + 1)}{(n + 1)!}\ - \ \frac{2n * ... * n}{(n + 1)!}$
$= \frac{2n*...*(n + 1)(n + 1 - n)}{(n + 1) !}$
$= \frac{ C_{2n} ^{n}}{n +1}$

回到本题：

$\frac{ C_{2n} ^{n}}{n +1}$ 的数值是很大的，而本题需要输出真实数值

所以要用到高精度乘法，而本题的 $n$ 最多是60000，需要用到一些方式优化高精度计算

压位
将组合数计算转化到质数相乘的运算

压位：

在写高精度乘法的时候将原本 $/10$ 和 $%10$ 的部分改成 $/ 10000$ 和 $%10000$ ,这样每一位就代表10000进制数（压了4位）

用上long long最多可以压8位

这样计算速度会更快，然后注意一下输出方式

具体看代码实现

组合数计算转化到质数相乘的运算：

我们分别将分子和分母的阶乘分解质数

然后分别将分子分母对应相同质数的数量相减

最后将剩余的质数累乘起来就是答案

这样位数的增长曲线会更加平滑优化时间复杂度

时间复杂度 $O(n^2)$

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 120010;
int primes[N],cnt;
bool st[N];
int power[N];
int n;

void init(int n)
{
    for(int i = 2;i <= n;i ++)
    {
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0;primes[j] <= n / i;j ++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int get(int x,int p)
{
    int res = 0;
    while(x)
    {
        res += x / p;
        x /= p;
    }
    return res;
}

void mul(vector<LL> &a,int b)
{
    LL t = 0;
    for(int i = 0;i < a.size();i ++)
    {
        a[i] = a[i] * b + t;
        t = a[i] / 100000000;//压8位
        a[i] %= 100000000;
    }
    while(t)
    {
        a.push_back(t % 100000000);
        t /= 100000000;
    }
}

void out(vector<LL> a)
{
    printf("%lld",a.back());//第一个数直接输出
    for(int i = a.size() - 2;i >= 0;i --) printf("%08lld",a[i]);//后面的数输出八位，不足前面补0
}

int main()
{
    init(N - 1);
    scanf("%d",&n);
    for(int i = 0;primes[i] <= n * 2 && i < cnt;i ++)
    {
        power[primes[i]] = get(n * 2,primes[i]) - get(n,primes[i]) * 2;
        //将分子阶乘中primes[i]的个数减去分母阶乘中primes[i]的个数（相当于约分的过程）
    }
    int k = n + 1;
    for(int i = 0;primes[i] <= k / primes[i];i ++)
        if(k % primes[i] == 0)
        {
            while(k % primes[i] == 0)
            {
                k /= primes[i];
                power[primes[i]] --;
            }
        }
    //处理n + 1的质数个数
    if(k > 1) power[k] --;
    vector<LL> res;
    res.push_back(1);
    for(int i = 0;primes[i] <= n * 2 && i < cnt;i ++)
        while(power[primes[i]])
        {
            mul(res,primes[i]);//累乘
            power[primes[i]] --;
        }
    out(res);
    return 0;
}

总结：

卡特兰数公式
卡特兰数的推导
高精度压位
组合数计算转化为质数相乘运算