题解

思路

一个确定括号串的深度，等于某个分割点左边左括号数和右边右括号数的较小值的最大值。换言之，深度至少为 $k$，当且仅当存在第 $k$ 个左括号，并且它右侧至少还有 $k$ 个右括号。

问号不超过 $18$ 时可枚举所有替换。$n\le200$ 时可对每个深度阈值重新计算前后缀分布。满分算法一次预处理所有前后缀计数，复用到全部阈值。

做法

令 $L[i][j]$ 表示前 $i$ 个字符恰有 $j$ 个左括号的替换方案数，$R[i][j]$ 表示后缀 $i\ldots n-1$ 恰有 $j$ 个右括号的方案数。再对 $R$ 的计数维做后缀和，得到后缀中至少有 $j$ 个右括号的方案数。

固定深度阈值 $k$。对每种完整替换，若其深度至少为 $k$，第 $k$ 个左括号的位置唯一。枚举该位置 $i$：前缀需要恰有 $k-1$ 个左括号，位置 $i$ 能取左括号，右侧需要至少 $k$ 个右括号。三部分相乘并求和，就得到深度至少为 $k$ 的替换数。

最后利用非负整数恒等式

$$\sum_s \operatorname{depth}(s)=\sum_{k\ge1}\#\{s:\operatorname{depth}(s)\ge k\}$$

求出答案。

复杂度

时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。