概念
以下看似毫不相关的问题均属于 Catalan 数列：
- \(n\) 个节点构成的无标号、区分左右儿子的二叉树数量为 \(Cat_n\)
- \(n\) 个节点构成的无标号、区分儿子的有根树数量为 \(Cat_{n - 1}\)
- \(n\) 个左括号与 \(n\) 个右括号组成的合法序列有 \(Cat_n\) 种
- \(n\) 个元素按照大小进栈，合法的出栈序列有 \(Cat_n\) 种
- 将凸 \(n\) 边形用 \(n - 3\) 条对角线将其分割为互不重叠的 \(n - 2\) 个三角形的方案数为 \(Cat_{n - 2}\)
- 从 \((0,0)\) 出发，每次沿正方向走，到达 \((n,n)\) 且不接触直线 \(y=x\) 的路径数量为 \(Cat_n\)
- 以圆上的 \(2n\) 个点为端点，连互不相交的 \(n\) 条弦的方案数为 \(Cat_n\)
- 将 \(1 \sim 2n\) 中的数不重不漏地填入 \(2 \times n\) 的矩阵，每个数字大于其左边和上面数字的方案数 \(Cat_n\)
卡特兰序列的前几项为：
| \(Cat_0\) | \(Cat_1\) | \(Cat_2\) | \(Cat_3\) | \(Cat_4\) | \(Cat_5\) | ... |
|---|---|---|---|---|---|---|
| \(1\) | \(1\) | \(2\) | \(5\) | \(14\) | \(42\) | ... |
实现
关于卡特兰数的常见公式：
\[\begin{aligned}
Cat_n &= \frac{\dbinom{2n}{n}}{n+1} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (n>2)
\\
Cat_n &= \dbinom{2n}{n} - \dbinom{2n}{n - 1}
\\
Cat_n &= \frac{Cat_{n-1}(4n-2)}{n+1}
\\
Cat_n &=
\begin{cases}
\sum_{i = 1}^{n} Cat_{i - 1} \times Cat_{n-i} & (n>2)
\\
1 & (n=0,1)
\end{cases}
\\
\end{aligned}
\]
应用
本题是求凸多边形三角划分，直接求 \(Cat_n\) 即可
\(1 \sim 2n\) 均匀分给 \(A, B\) 两人，排序后比较大小， \(A\) 大记 \(0\) ， \(B\) 大记 \(1\) ，给定一个 \(01\) 串，求可能的分配方案数 \(\bmod 998244353\)
对于所有数据， \(1 \leq n \leq 10^5\)
对于一个极长连续 \(1\) 段，则对于任意一个前缀， \(B\) 所占有的数字均大于 \(A\) 所占有的数字，不难发现这可以转化为括号匹配的方案数，极长连续 \(0\) 段同理，答案即为每一个极长连续段的卡特兰数之积
#include <bits/stdc++.h>
using namespace std;
const int Mod = 998244353;
const int N = 1e5 + 7;
int cat[N], inv[N];
char s[N];
int n, ans = 1;
inline void init() {
inv[0] = inv[1] = 1;
for (int i = 2; i <= n + 1; ++i)
inv[i] = 1ll * (Mod - Mod / i) * inv[Mod % i] % Mod;
cat[0] = cat[1] = 1;
for (int i = 2; i <= n; ++i)
cat[i] = 1ll * cat[i - 1] * (4ll * i % Mod - 2) % Mod * inv[i + 1] % Mod;
}
signed main() {
scanf("%d%s", &n, s + 1);
init();
for (int i = 1, pos = 1; i <= n; i = pos) {
while (s[i] == s[pos] && pos <= n)
++pos;
ans = 1ll * ans * cat[pos - i] % Mod;
}
printf("%d", ans);
return 0;
}