与之前的类似，就是讲一点技巧，但是比较乱，凑合着看吧。

字符串

括号匹配

• 几何意义：考虑令 ( 为 $+1$ 变换，令 ) 为 $-1$ 变换，然后对这个 $+1/-1$ 构成的变换序列在平面直角坐标系中变成一张从原点出发的折线图，也就是令 ( 为上斜坡，) 为下斜坡。
• 如何判断合法：转化完之后，我们只需要判断构成折线是否仅在 $x$ 轴或 $y$ 轴或第一象限内且是否最终回到 $0$。
• 扩展：如果不是从原点开始，令开始时 $y$ 坐标为 $k$，则判断每个位置是否都 $\ge k$ 且最终回到 $k$。这可以用来判断子串是否为合法括号序列。

例 1：

给定一个合法括号序列 $S$。
定义好的序列为由 ? 和 ( 和 ) 构成的序列（可以不包含其中任意数量个），且存在唯一一种方式将每个 ? 依次替换为 ( 或 ) 后，得到合法括号序列。
问如果每个位置都有 $\frac{1}{2}$ 的概率变为 ?，那么有多大的概率变为好的序列。
对 $998244353$ 取模，$|S|\le 10^6$。

做法：

1. 先将概率转化成方案数。
2. 注意到对于一个好的序列，直接把它变为输入的序列一定是一种方案，于是变为怎样指定某些位置翻转但是每一个位置都不能翻转的方案数。
3. 考虑转化成几何意义后怎么做，那就变成了考虑什么时候某个位置可以翻转但是翻转后一定无法得到合法括号序列。
4. 上述情况当且仅当：
   1. 不匹配，也就是如果翻转那么一定无法使得左右括号数量相同，这会导致无法回到 $0$，出现情况当且仅当对于 (，后面不存在一个位置 ) 也可以被翻转，或对于 )，前面不存在 ( 也可以被翻转。（注意到一旦存在就一定会贡献给某个异类括号，因此即使不贡献给枚举的位置也会导致无解）。
   2. 翻转之后跑到 $x$ 轴下面去了，这当且仅当翻转的位置为 ( 且直到下一个可以被翻转的 ( 前存在某个位置的原本的 $y$ 坐标 $\le 1$。
5. 考虑对这个怎么计数，首先我们能得到一些结论：
   1. 不会存在 ...)...(... 然后两个括号都变成 ?，因为他们既可以跟原来的括号匹配，又可以翻转过来，跟内部的匹配或是跟对方匹配，可以证明这两种方案之一一定合法，转化成折线图后易证。也就是说，一定是一些 ( 被选择，然后一些 ) 被选择。
   2. 一个 (可以被标记为 ? 当且仅当以下条件之一成立：
      1. 它到后一个可以被翻转的 ) 中存在某个位置的 $y$ 坐标 $\le 1$，翻转后会使得这个点坐标 $-2$，于是不合法，于是乎可以标记。
      2. 它后面没有标记为 ? 的 ) 了，这样如果翻转它一定回不到 $0$。
6. 于是什么时候可以放 (，什么时候可以放 ) 都已经确定好了，那么直接计数即可，我的做法是先存储 $y$ 坐标 $=0$ 的的配对的括号，枚举第一个 ) 被选择的区间，计算它的贡献，然后再在里面找坐标 $=1$ 的括号，然后对于这样的一个位置，计算它的贡献。
7. 具体来说，$y=0$ 的贡献是左端点随便取或不取，然后如果这个区间里面选择取 (，那么除掉最后一个 ) 以外的所有 ) 都不能取（我们先没考虑 $y=1$ 的影响），最后一个 ) 必须取。
8. 接着考虑，$y=1$，那么它包含的前面一段 ( 选择后，这段的 ) 不能选，由于是计算比 $y=0$ 更多的贡献，所以不计算选 ) 和部分选 ( 的情况以免算重，我们只需要计算不会被 $y=0$ 包含的部分，也就是这个位置之后可以有 ) 被选择，加入答案即可。

实现可能较为困难，读者不妨尝试。原题是这个比赛的 T2，作者从 8:40 到 19:00 断断续续写了至少 7 小时才 A 掉。

总结：这题本质上是在考虑处理第一个 ) 被选择的位置，考虑不同位置会有什么影响，然后按照 $y\le 1$ 来分段处理。