CF2063F1/CF2063F2 Counting Is Not Fun 题解

zrl123456 · 2025-10-03 21:12:33 · 题解

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

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

题目简述：

• 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，我们发现：

这两个显然可以 \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_i\leftarrow 0。
同时，根据：

我们得到：

现在我们需要快速求出 lst_i。
注意到删去括号等价于把括号合并到它的 lst 上，我们使用并查集维护即可。
然后做完了。
时间复杂度为 \Theta(n\alpha(n)+n\log m)（递推 Catalan 数可以做到 \Theta(n\alpha(n))，爆标了），空间复杂度为 \Theta(n)。
:::::success[code] F1
F2
:::::