火车进出栈问题 题解

来源 卡特兰数

个人评价（一句话描述对这个题的情感）

…~%?..,# *'☆&℃$︿★?

1 题面

一列火车n节车厢，依次编号为1,2,3,…,n。每节车厢有两种运动方式，进栈与出栈，问n节车厢出栈的可能排列方式有多少种。

输入

一个数，n(n<=60000)

输出

一个数s表示n节车厢出栈的可能排列方式

样例

样例输入1

3

样例输出1

5

2 分析题面

求卡特兰数的第n项，不取模

有两种方式，都能推出这是一道纯卡特兰数题

2.1 递推

“计数原理中的乘法原理，总的方案数等于第一步的方案数和第二步的方案数之积”

以编号为 $k$ 的车厢为界，将列车分为两部分

一部分是在第 $k$ 节车厢出栈前出栈的车厢，一部分是在第 $k$ 节车厢出栈后出栈的车厢

设在第$k$节车厢出栈前出栈的车厢的数量为 $i(0<=i<=k)$

则在第 $k$ 节车厢出栈后出栈的车厢的数量为 $(k-i-1)$

前 $i$ 节车厢出栈的可能性数量有 $F(i)$

后 $(n-i-1)$ 节车厢出栈的可能性数量有 $F(k-i-1)$

所以总的数量为 $F(i)\times F(k-i-1)$

由于当只有0节车厢（即一节车厢也没有）时，方案数为$1$

所以，$F(0)=1$

因此，我们可以得到一个递归公式：

$F(k)=F(0)\times F(k-1)+F(1)\times F(k-2)+F(2)\times F(k-3)+...+F(k-2)\times F(1)+F(k-1)\times F(0)$

$其中k>=1，F(0)=1$

看出什么了吗？

其实这道题就是Catalan number！！

只不过n的初值少$1$。。。

2.2 组合数

首先，每一种进出栈的顺序都与出栈序列一一对应

也就是说，如果我们用$+1$表示进栈，$-1$表示出栈

那么举个例子：

出栈序列 $1,3,4,2$ 与进出栈顺序 $+1,+1,-1,+1,+1,-1,-1,-1$ 是对应的

那么对$n$个数的序列，总的进出栈顺序不是就是给$2n$个$1$前面挑$n$个添加$+$号

其他的添加$-$号，共${\mathrm{C}}_{2n}^n$种吗？

答案是否定的，这是因为出栈的前提是有进栈

于是要求每个排列中的前若干项和均不为负数

即排列$$1,-1,-1,1,1,-1,-1,1$$是无效的

那么无效的排列到底有多少呢？

考虑$M$是所有无效的排列构成的集合

考虑其中第一次发现排列无效的时候，也就是第一次发现其前若干项和为$-1$的时候

此时我们将包含使得前若干项和为$-1$的这一项开始的之前的所有项全都取相反数

那么就会得到一个新的排列

这个排列包含$n+1$个$+1$，以及$n-1$个$-1$

设所有这样的排列构成集合$N$

显然，这个$M\to N$的映射是一一映射的

（$N$中的每一个排列从第一项往后累积求和的时候必然会出现和为$+1$的情形，

此时将排列中使得和为$+1$的这一项连同之前的所有项全部取相反数，

那么就会得到$M$中的一个排列）

因此无效的排列共有${\mathrm{C}}_{2n}^{n-1}$个．

综上，所有不同的出栈序列总数为${\mathrm{C}}_{2n}^n-{\mathrm{C}}_{2n}^{n-1}$，即$\frac{{\mathrm{C}}_{2n}^n}{n+1}$

也就是卡特兰数！

3 代码实现（注释）

3.1定义

//Cn为卡特兰数的第n项
int n;//输入
int ans[N];//高精度答案数组
int len=1；//答案的位数
int p[N];//质数
int c[N];//c[i]是Cn中p的个数
int tot;//2*n中质数的个数
bool vis[N];//埃氏筛标记数组

3.2 输入

就输入一个n

scanf("%d",&n);//输出的

3.3 预处理

预处理质数，这里我用的是埃氏筛（用欧拉筛也行）

 for(int i=2;i<=n*2;i++) {//预处理1-2n之间的质数if(!vis[i]) {//vis数组没有被标记过p[++tot]=i;//统计质数for(int j=i;j<=N;j+=i) vis[j]=1;//大量优化复杂度！}//就是埃氏筛
} 

3.4 高精度

这个乘法还是挺显然的吧

void jing(int x) {//高精乘法 乘xfor(int i=1;i<=len;i++) ans[i]*=x;//直接乘xlen+=6;//长度最多+6for(int i=1;i<=len;i++) {//每一位处理ans[i+1]+=ans[i]/10;ans[i]%=10;}//进位while(!ans[len]) len--;//将多加的长度剪掉
}

3.5 计算

先考虑(n)小一点的做法，我们可以直接用卡特兰数的线性递推公式:

$f_n=f_{n-1}\frac{4n-2}{n+1}$

然后看一眼数据，显然不行！

然后考虑一下优化

我们要换一个思路，应该用这个公式:

$C_n=\frac{C_{2n}^n}{n+1}$

大力感谢zjy提供的思路！！！

3.5.1 转换公式

首先，由卡特兰数的通项公式$C_n=\frac{C_{2n}^n}{n-1}$

$$\begin{gathered} \Rightarrow C_n=\frac{!(2n)/(!n{)}^2}{n+1} \\ \Rightarrow C_n=\frac{!(2n)}{(!n{)}^2(n+1)} \end{gathered}$$

最终表示为阶乘形式：$C_n=\frac{(2n)!}{n!(n-1)!}$

再看一下算数基本定理：

$A=p_1^{a_1}\ast p_2^{a_2}\ast ...\ast p_k^{a_k}$

注意到卡特兰数每一项都一定是一个整数

也就是说，如果将如上公式的分子分母分解质因数

那么分母的各个因式指数上一定是可以被分子的各个因式相减抵消的

但是分子分母都是存在阶乘结构的，那么就考虑然后对某个数的阶乘分解质因数

3.5.2 分解阶乘

其次，一个质数$p[i]$在$n！$中可分解的个数为$n/p[i]$

口胡一下证明：

$n!=1\times 2\times 3\times ...\times (n-1)\times n$

所以在$n!$中（即$1-n$中）是$p[i]$的倍数的个数显然为$n/p[i]$个

然后，在$n!$中可被至少包含$k$的$m$次方的个数$x[m]$为：

$x[m]=(2n)/p[i{]}^m-n/p[i{]}^m-(n-1)/p[i{]}^m$

最终，$C_n$中包含$p[i]$的个数为

所有$n$能被$p[i{]}^m$整除的$m$的$x[m]$之和

所以$c[i]={\sum }_{j=1}^{m}x[j]$

口胡证明如下：

---

证明1：

不妨设$k^3|n!$且最多只能被$k$的3次方整除

当$m=1$时，$x[1]=(2n)/k-n/k-(n-1)/k$

当$m=2$时，$x[2]=(2n)/k^2-n/k^2-(n-1)/k^2$

当$m=2$时，$x[3]=(2n)/k^3-n/k^3-(n-1)/k^2$

由于$x$数组的定义是$x[m]$是$n!$（即$1-n$）中至少包含$k$的$m$次方的数的个数

所以，$n!$中只包含k的1次方的数的个数为$x[1]-x[2]$

同理可得，$n!$中只包含k的1次方的数的个数为$x[2]-x[3]$

又因为$n!$且最多只能被$k$的3次方整除，所以$n!$中只包含k的1次方的数的个数为$x[3]$

所以总的包含的$k$的个数$c$为

$c=(x[1]-x[2])\times 1+(x[2]-x[3])\times 2+x[3]\times 3$

化简后得：$c=x[1]+x[2]+x[3]$

根据数学归纳法，

$c[i]={\sum }_{j=1}^{m}x[j]$

证毕

---

证明2：

对于$n!=1\times 2\times ...\times n$，考虑它存在多少个质因子$p$

• 显然有$\lfloor \frac{n}{p}\rfloor$个数有至少$1$个因子$p$
• 那么，有$\lfloor \frac{n}{p^2}\rfloor$个数有至少$2$个因子$p$
• $...$
• 依次类推，有$\lfloor \frac{n}{p^x}\rfloor$个数有至少$x$个因子$p$

---

循环枚举每一个质因子，对于每一个质因子

所以我们通过枚举$1-2n$的质数来进行拆分

再将拆分出的$p[i{]}^{c[i]}$乘进$ans$中

就ok了

可得代码：

 for(int i=1;i<=tot;i++) {//枚举质数int now=p[i];while(now<=n*2) {//c[i]指出现的个数c[i]+=n*2/now-n/now-(n+1)/now;now*=p[i];}while(c[i]--) jing(p[i]);//乘p[i]的c[i]次方
}

3.6 输出

输出高精ans数组即可

for(int i=len;i>=1;i--) {printf("%d",ans[i]);
}//注意要倒着输出

3.7 总体代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1200000;
int n,ans[N],len=1,p[N],c[N],tot;
bool vis[N];
void jing(int x) {for(int i=1;i<=len;i++) ans[i]*=x;len+=6;//最多加六位（*的数小于等于n*2）for(int i=1;i<=len;i++) {ans[i+1]+=ans[i]/10;ans[i]%=10;}while(!ans[len]) len--;
}//高精度乘法
int main(){scanf("%d",&n);//初始化ans[1]=1;//初始化高精ans=1for(int i=2;i<=n*2;i++) {if(!vis[i]) {p[++tot]=i;//统计质数for(int j=i;j<=N;j+=i) vis[j]=1;//排除合数//原因显然，质数的k(k≠1)倍肯定不是质数,证明如下：//质数的定义是：一个数只有1和它本身两个因数，称这个数叫做质数//质数(p[i])的k(k≠1)倍已经有了k和p[i]两个(不是1和它本身)的因数//综上所述，质数的k(k≠1)倍肯定不是质数}//埃氏筛求2*n以内的质数} //预处理for(int i=1;i<=tot;i++) {//枚举质数int now=p[i];while(now<=n*2) {//c[i]指出现的个数c[i]+=n*2/now-n/now-(n+1)/now;now*=p[i];}while(c[i]--) jing(p[i]);//高精乘法}//计算for(int i=len;i>=1;i--) {printf("%d",ans[i]);}//输出return 0;
}

4 总结

​ 就是卡特兰数高精的一种奇妙并且码量少的一种写法！

完结撒花❀
★,°:.☆(￣▽￣)/$:.°★ 。