Catalan (卡特兰数)
前置知识：
1、排列数公式： A n m = n ( n − 1 ) ( n − 2 ) . . . ( n − m + 1 ) A^m_n=n(n-1)(n-2)...(n-m+1) Anm=n(n−1)(n−2)...(n−m+1)
引入阶乘 n ! n! n!以后，排列数公式变形如下：
A n m = n ( n − 1 ) ( n − 2 ) . . . ( n − m + 1 ) = n ( n − 1 ) ( n − 2 ) . . . ( n − m + 1 ) ( n − m ) . . . 3 ∗ 2 ∗ 1 ( n − m ) . . . 3 ∗ 2 ∗ 1 = n ! ( n − m ) ! A^m_n=n(n-1)(n-2)...(n-m+1)=\frac{n(n-1)(n-2)...(n-m+1)(n-m)...3*2*1}{(n-m)...3*2*1}=\frac{n!}{(n-m)!} Anm=n(n−1)(n−2)...(n−m+1)=(n−m)...3∗2∗1n(n−1)(n−2)...(n−m+1)(n−m)...3∗2∗1=(n−m)!n!
**注意：**为了保证公式在 n = m n=m n=m时成立，特规定 0 ! = 1 0!=1 0!=1
2、组合数公式： C n m = A n m A m m = n ( n − 1 ) ( n − 2 ) . . . ( n − m + 1 ) m ! = n ! m ! ( n − m ) ! C^m_n=\frac{A^m_n}{A^m_m}=\frac{n(n-1)(n-2)...(n-m+1)}{m!}=\frac{n!}{m!(n-m)!} Cnm=AmmAnm=m!n(n−1)(n−2)...(n−m+1)=m!(n−m)!n!
其它性质：
C n m = C n n − m C^m_n=C^{n-m}_n Cnm=Cnn−m (对称)
C n m = C n − 1 m + C n − 1 m − 1 C^m_n=C^m_{n-1}+C^{m-1}_{n-1} Cnm=Cn−1m+Cn−1m−1
C n 0 + C n 1 + C n 2 + . . . + C n n = 2 n C^0_n+C^1_n+C^2_n+...+C^n_n=2^n Cn0+Cn1+Cn2+...+Cnn=2n
注意： C n 0 = 1 C^0_n=1 Cn0=1
Catalan:
卡特兰数是组合数学中的一种著名数列，通常用如下通项式表示(为了不与组合数C 冲突，本文用 f f f 表示卡特兰数)： f ( n ) = C 2 n n n + 1 f(n)=\frac{C^n_{2n}}{n+1} f(n)=n+1C2nn
通项式变形： f ( n ) = C 2 n n − C 2 n n − 1 f(n)=C^n_{2n}-C^{n-1}_{2n} f(n)=C2nn−C2nn−1
卡特兰数递推式： f ( n ) = ∑ i = 0 n − 1 f ( i ) ∗ f ( n − i − 1 ) f(n)=\sum\limits^{n-1}_{i=0}f(i)*f(n-i-1) f(n)=i=0∑n−1f(i)∗f(n−i−1)
与卡特兰数相关的问题：
1、 1 , 2 , . . . , n 1,2,...,n 1,2,...,n经过一个栈，形成的合法出栈序列的数量为 c a t n cat_n catn
2、 n n n个左括号和 n n n个右括号组成的合法括号序列的数量为 c a t n cat_n catn
3、 n n n个结点构成的不同二叉树的数量为 c a t n cat_n catn
4、买票排队问题，票价为 x x x元，现在有 n n n个顾客用面值为 x x x的钱币购买，还有 n n n个顾客用面值为 x ∗ 2 x*2 x∗2的钱币购买，商家起初没有钱找零。此时形成的合法排队(商家可以给所有该找零的顾客找零)方案数量为 c a t n cat_n catn
5、 n n n边形 ( n > = 3 ) (n>=3) (n>=3)切割 n − 3 n-3 n−3刀，要求剩下的图形都为三角形，切割的方案数为 c a t n cat_n catn
6、在平面直角坐标系上，每一步只能向上或向右走，从 ( 0 , 0 ) (0,0) (0,0)走到 ( n , n ) (n, n) (n,n)并且除了两个端点外不接触 y = x y=x y=x的路线数量为 2 c a t n − 1 2cat_{n-1} 2catn−1
实际做Catalan数的题目时，数值会非常大，通常配合高精度运算，通过阶乘分解的方法可以省去除法运算，只用高精度乘法模拟即可
阶乘分解
给定整数 N ( 1 < = N < = 1 0 6 ) N(1<=N<=10^6) N(1<=N<=106),试把阶乘 N ! N! N!分解质因数，按照算数基本定理的形式输出分解结果中的 p i p_i pi和 c i c_i ci即可( p i p_i pi代表第 i i i个质因子， c i c_i ci代表第 i i i个因子的个数)
若 1 ∼ N 1\thicksim N 1∼N每个数分别分解质因数，再把结果合并，时间复杂度过高，为 O ( N N ) O(N\sqrt{N}) O(NN )。显然， N ! N! N!的每个质因子都不会超过 N N N，我们可以先筛选出 1 ∼ N 1\thicksim N 1∼N 的每个质数 p p p，然后考虑N!中一共包含多少个质因子 p p p
N ! N! N!中质因子 p p p 的个数就等于 1 ∼ N 1\thicksim N 1∼N每个数包含质因子 p p p 的个数之和。在 1 ∼ N 1\thicksim N 1∼N中， p p p 的倍数，即至少包含 1 1 1 个质因子 p p p 的显然有 ⌊ N p ⌋ \lfloor \frac{N}p \rfloor ⌊pN⌋个。而 p p p 的倍数，即至少包含 2 2 2个质因子 p p p 的有 ⌊ N p 2 ⌋ \lfloor \frac{N}{p^2} \rfloor ⌊p2N⌋个。不过其中的 1 1 1个质因子已经在 ⌊ N p ⌋ \lfloor \frac{N}p \rfloor ⌊pN⌋里统计过，所以只需要再统计第 2 2 2个质因子，即累加上 ⌊ N p 2 ⌋ \lfloor \frac{N}{p^2} \rfloor ⌊p2N⌋，而不是 2 ∗ ⌊ N p 2 ⌋ 2 *\lfloor \frac{N}{p^2} \rfloor 2∗⌊p2N⌋。
综上所述， N ! N! N!中质因子 p p p 的个数为:
⌊ N p ⌋ + ⌊ N p 2 ⌋ + ⌊ N p 3 ⌋ + . . . + ⌊ N p ⌊ l o g p N ⌋ ⌋ = ∑ p k ⩽ N ⌊ N p k ⌋ \lfloor \frac{N}p \rfloor+\lfloor \frac{N}{p^2} \rfloor+\lfloor \frac{N}{p^3} \rfloor+...+\lfloor \frac{N}{p^{\lfloor {log_pN} \rfloor}} \rfloor=\sum\limits _{p^k \leqslant N} \lfloor \frac{N}{p^k} \rfloor ⌊pN⌋+⌊p2N⌋+⌊p3N⌋+...+⌊p⌊logpN⌋N⌋=pk⩽N∑⌊pkN⌋
对于每个 p p p，只需要 O ( l o g N ) O(logN) O(logN)的时间计算上述和式。故对整个 N ! N! N!分解质因数的时间复杂度为 O ( N l o g N ) O(NlogN) O(NlogN)
1、火车进出栈问题
卡特兰数： f ( n ) = C 2 n n n + 1 f(n)=\frac{C^n_{2n}}{n+1} f(n)=n+1C2nn , C 2 n n = ( 2 n ) ! n ! n ! C^n_{2n} = \frac{(2n)!}{n!n!} C2nn=n!n!(2n)!
把 ( 2 n ) ! (2n)! (2n)!的所有质因子 p i p_i pi以及数量 c i c_i ci 分别存放到两个数组中。用同样的方法计算出 n ! n ! n!n! n!n!并从这两个数组的对应位置减去对应数量。之后再分解 n + 1 n+1 n+1,也从这两个数组中减去对应数量。(结果为所有分母都被约分掉，相当于去掉了除法操作，证明略)
最后高精度乘法模拟两个数组运算即可
/*************************************************************************
> File Name: 130.c
> Author: Luzelin
> Mail:
> Created Time: Sun Nov 28 10:59:19 2021
************************************************************************/
#include <stdio.h>
#define N 60000
int prime[N * 2 + 5], nums[N * 2 + 5], cnt;
//线性筛出小于等于n*2的所有质数
void Get_prime(int n) {
for (int i = 2; i <= n; ++i) {
if (prime[i] == 0) prime[cnt++] = i;
for (int j = 0; j < cnt && i * prime[j] <= n; ++j) {
prime[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
return ;
}
//阶乘分解
//n!中存在质因子p的个数
int Get_div(int n, int p) {
int cnt = 0;
//除数乘p等价于被除数除p
while (n > 1) {
cnt += n / p;
n /= p;
}
return cnt;
}
//高精乘模拟(压位优化，四位)
void mul(int *vec, int x) {
int t = 0;
for (int i = 1; i <= vec[0]; ++i) {
vec[i] = vec[i] * x + t;
t = vec[i] / 10000;
vec[i] %= 10000;
}
while (t) {
vec[++vec[0]] = t % 10000;
t /= 10000;
}
return ;
}
int main() {
int n;
scanf("%d", &n);
Get_prime(n * 2);
//遍历所有可能是(n*2)!的质因子，如果存在把个数存放到相应位置。之后相对位置减去n!的质因子个数
for (int i = 0; i < cnt; ++i) {
int ind = prime[i];
nums[ind] = Get_div(n * 2, ind) - Get_div(n, ind) * 2;
}
//减去n+1含有的因子
int x = n + 1;
for (int i = 0; x > 1; ++i) {
while (x > 1 && x % prime[i] == 0) {
--nums[prime[i]];
x /= prime[i];
}
}
int vec[1000000] = {1, 1};
for (int i = 2; i <= 2 * n; ++i) {
for (int j = 1; j <= nums[i]; ++j) {
mul(vec, i);
}
}
//第一位不需要补前导0
printf("%d", vec[vec[0]]);
for (int i = vec[0] - 1; i > 0; --i) {
printf("%04d", vec[i]);
}
putchar('\n');
return 0;
}