题解：CF1830C Hyperregular Bracket Strings

· · 题解

我们可以利用卡特兰数在 O(n) 时间内预处理，从而 O(1) 查询长度为 n 的合法括号序列个数。

观察到：在最终合法的括号序列中，任意一对匹配的括号必须被完全相同的区间集合包含。这是因为，若某个区间包含了其中一个括号，则它必须同时包含与之匹配的另一个括号，否则该区间内的子串无法形成合法括号序列。因此，我们要找到被包含区间集合一样的点。

可以用前缀异或和（类似哈希）：

  1. 为每个区间随机一个值 w_i。
  2. 创建一个数组代表前缀异或和 v[1 \dots n]。
  3. 对于每个区间 [l_i, r_i]：
  4. 计算前缀异或 s_i = \bigoplus_{j=1}^{i} v[j]，则 s_i 即为位置 i 的哈希值，表示包含 i 被包含区间的 w_i 的异或和。
  5. 统计每个哈希值出现的次数，每个哈希值对应的数量就是要用卡特兰数求合法括号串的长度。

由于随机权值，不同区间集合哈希碰撞的概率极低，可以忽略（如果觉得不保险，可以随机两个值）。

时间复杂度为 O(n)。