本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-03 21:12:33

:::::info[闲话] 模拟赛的题，太菜了，不会，打了 30pts 部分分（其实就是 F1）跑路了。
看完 F2 题解中 Ri 的 idea 大受震撼。
::::: :::::info[题目基本信息] 考察：

• F1：Catalan 数，组合数学（$2400$）。
• F2：Catalan 数，组合数学，并查集（$2700$）。

题目简述：
$t$ 组数据，每组数据以一定顺序给定一个长度为 $2n$ 的匹配括号序列的 $n$ 组括号匹配对，当 $\forall i\in[0,n]$ 时，求有多少长度为 $2n$ 的匹配括号序列使得它的括号匹配对中含有第 $j$（$1\le j\le i$）组括号匹配对（对 $998244353$ 取模）。
数据范围：

1. F1：

• $1\le t\le 1000$
• $2\le n\le 5000$
• 对于单个测试点，$\displaystyle\sum n\le 5000$

2. F2：

• $1\le t\le 10^4$
• $2\le n\le 3\times 10^5$
• 对于单个测试点，$\displaystyle\sum n\le 3\times 10^5$ :::::

F1 部分：

我们有一个结论：长度为 $2n$ 的匹配括号序列的个数为 $C_n$（这里的 $C_n$ 指 Catalan 数的第 $n$ 项）。
:::::success[证明] 太经典了，懒得写，右转 oiwiki。
::::: 那么我们设最后的答案序列为 $\{ans_n\}$，根据上文我们得到 $ans_0=C_n$。
现在我们考虑从 $ans_i$ 推导到 $ans_{i+1}$（这里 $i\in[0,n)$）：

其中黑色虚线表示的是当前要加入的第 $i$ 对括号匹配对，红色实线表示的是离它最近的包含它的括号匹配对（记为 $lst_i$），蓝色虚线表示的是它所包含的括号匹配对，设第 $k$ 对括号匹配对内未被其它括号匹配对包含的位置的数量为 $siz_k$，那么我们可以得到：
$$ans_{i+1}\leftarrow \frac{ans_iC_{(siz'{lst_i}-siz{i}-2)\div 2}C_{siz_i\div 2}}{C_{siz'_{lst_i}\div 2}}$$ 这里，$siz'_k$ 表示还未被更新的 $siz_k$，那么：
$$siz_k\leftarrow siz'_k-siz_i-2$$ :::::success[证明] 显然，一对括号匹配对左右拼起来是一个匹配括号序列，它的里面也是一个匹配括号序列，通过这个性质我们可以得出上面的式子。
::::: 现在，我们还需要找到 $lst_i$，同时计算 $siz_i$，考虑将 ( 当作 $+1$，) 当作 $-1$，我们发现：

• $l_{lst_i}$（$lst_i$ 的左括号位置，$r$ 同理）是从右往左第一个 $p$ 使得 $[p,l_i)$ 的权值和大于 $0$ 的，因为它是第一个统计不到 $r$ 的。
• $siz_i$ 是 $p$（$p\in(l_i,r_i)$）满足 $(l_i,p)$ 的权值和等于 $0$ 的数量。

这两个显然可以 $\Theta(n)$ 统计（也可能可以用数据结构优化），这样我们就解决了 F1。
时间复杂度为 $\Theta(n^2+n\log m)$（$m=998244353$ 是模数，可以优化成 $\Theta(n^2+\log m)$ 但没必要），空间复杂度为 $\Theta(n)$。

F2 部分：

注意到上面 F1 的做法正推优化可能比较麻烦，需要上数据结构（诸如线段树，官解用了平衡树），所以我们考虑倒推删括号。
显然 $ans_n=1$，现在我们考虑从 $ans_i$ 推导到 $ans_{i-1}$。
还是上面的图，我们考虑删去黑色虚线表示的括号匹配对，这时：
$$siz_{lst_i}\leftarrow siz'{lst_i}+siz_i+2$$ 同时由于括号被删去，$siz_i\leftarrow 0$。
同时，根据：
$$ans{i+1}\leftarrow \frac{ans_iC_{(siz'{lst_i}-siz{i}-2)\div 2}C_{siz_i\div 2}}{C_{siz'{lst_i}\div 2}}$$ 我们得到：
$$ans{i-1}\leftarrow \frac{ans_iC_{siz_{lst_i}\div 2}}{C_{(siz_{lst_i}-siz_{i}-2)\div 2}C_{siz_i\div 2}}$$ 现在我们需要快速求出 $lst_i$。
注意到删去括号等价于把括号合并到它的 $lst$ 上，我们使用并查集维护即可。
然后做完了。
时间复杂度为 $\Theta(n\lpha(n)+n\log m)$（递推 Catalan 数可以做到 $\Theta(n\lpha(n))$，爆标了），空间复杂度为 $\Theta(n)$。
:::::success[code] F1
F2
:::::