與之前的類似，就是講一點技巧，但是比較亂，湊合著看吧。

字符串

括號匹配

• 幾何意義：考慮令 ( 為 $+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$ 來分段處理。