题解

思路推导

把左括号视为 $1$，右括号视为 $-1$。合法性等价于所有前缀和非负。一次插入 “()” 会把插入位置处的高度 $h$ 展开成 $h,h+1,h$，插入 “)(” 则展开成 $h,h-1,h$。

暂时不除以每次位置选择的方案数。定义 $F_{k,h}$：从一个高度为 $h$ 的点开始，分配 $k$ 次带编号的插入操作后，所有始终不低于零的展开结构的概率权值和。空结构满足 $F_{0,h}=1$。

考虑这 $k$ 次操作中编号最小的一次。它把后续操作分到左侧、中间和右侧三块。若中间分到 $j$ 次操作，另外两块合计分到 $k-1-j$ 次，则编号的分配贡献组合数。左右两块都从高度 $h$ 开始，中间块根据第一次插入的类型从 $h+1$ 或 $h-1$ 开始。

做法

令

$$G_{s,h}=\sum_{a=0}^{s}\binom{s}{a}F_{a,h}F_{s-a,h}.$$

它把左右两块的分配一次性卷积起来。于是

$$F_{k,h}=\sum_{j=0}^{k-1}\binom{k-1}{j}G_{k-1-j,h} \left(pF_{j,h+1}+[h>0](1-p)F_{j,h-1}\right).$$

按 $k$ 递增计算 $F$；每完成一层，再由定义计算对应的 $G$。最终 $F_{n,0}$ 仍把每一步的所有插入位置都计入了权值。第 $i$ 次操作有 $2i-1$ 个等概率位置，因此答案还需乘上

$$\prod_{i=1}^{n}(2i-1)^{-1}.$$

所有运算均在模 $998\,244\,353$ 意义下进行。

对于前两个子任务，还可分别使用按定义维护所有不同括号串的指数枚举，以及不缓存 $G$、直接枚举左中右三块大小的四次动态规划。

正确性证明

以编号最小的插入操作为根后，任意生成历史唯一分解为左、中、右三个互不相交的子历史；反之，三个子历史与它们的编号分配也唯一还原一棵生成历史。组合数恰好统计编号在各块间的分配，因此转移无重无漏。

三个子结构的最低高度约束彼此独立。插入 “()” 时中间结构从 $h+1$ 开始；插入 “)(” 时中间结构从 $h-1$ 开始，并且仅当 $h>0$ 才可能合法。故转移准确统计所有从高度 $h$ 出发且不低于零的历史。

最后除以每一步插入位置数的乘积，正好把历史权值转为题目所述的真实概率，所以输出即为所求答案。

复杂度分析

共有 $O(n^2)$ 个状态，每个状态枚举 $O(n)$ 个分割位置。时间复杂度为 $O(n^3)$，空间复杂度为 $O(n^2)$。