算法一

先求出最小操作次数 $c$。

利用上午讲课提到过的方法，考虑直接对 $t$ 计数并贪心地匹配 $s$，这样我们能保证每个合法的 $t$ 只被算一次。

设 $f_{i,j,k}$ 表示填到 $t$ 的第 $i$ 位，贪心匹配到 $s$ 的第 $j$ 位，当前和为 $l$ 的方案数，容易写出转移，答案是 $f_{n+c,n,0}$。时间复杂度 $\mathcal{O}(n^3)$，期望得分 $64$ 分。

算法二（特殊性质 A）

还是需要考虑算重的问题，但是这次我们发现就不需要匹配了，看成用左括号把序列分成若干段，那么方案不同当且仅当有某一段右括号数量不同。于是我们可以依次枚举每一段填多少右括号。

具体来说，设 $f_{i,j}$ 表示从后往前第 $i$ 个左括号后共有 $j$ 个右括号的方案数，那么有 $f_{i,j} = \sum_{k=i-1}^{j} f_{i-1,k}$。利用前缀和优化即可做到 $\mathcal{O}(n^2)$。当然也可以直接算出 $n$ 对括号的合法括号序列数量，结合算法一可获得 $72$ 分。

算法三（特殊性质 B）

性质即 $t$ 可以划分成左括号和右括号两部分。

我们发现，划分之后这两部分是独立的。更具体一些，我们一定不会在左括号的部分再插入 $\texttt{)}$，也一定不会在右括号的部分再插入 $\texttt{(}$，否则方案一定不是最优的。

于是我们可以对两边分别做特殊性质 A 再把方案数乘起来。结合之前所有做法可以获得 $84$ 分。

算法四

有了特殊性质 B 的启示之后，让我们继续观察最优情况下操作的性质。

注意到，$t$ 中需要填左括号的部分和需要填右括号的部分一定不交。更具体一点，如果把 $t$ 拿到栈中做括号匹配，剩下的部分一定满足特殊性质 B。因此我们容易发现，一定存在某个位置，使得在所有可能的最优操作方案中：左括号在这个位置右边，右括号在这个位置左边。于是两个部分的方案数事实上是独立的。我们考虑算两遍，把方案数乘起来即可。

不妨考虑使用 DP 计算方案数。以下以填左括号为例，先求出每个右括号左侧至少要有多少左括号才能保证合法，设为 $c_i$。类似算法二，设 $f_{i,j}$ 表示第 $i$ 个右括号前共有 $j$ 个左括号的方案数，则有 $f_{i,j} = \sum_{k=c_{i-1}}^{r} f_{i-1,k}$。其中 $r$ 为原序列中右括号数量。

利用前缀和优化即可做到 $\mathcal{O}(n^2)$。期望得分 $100$ 分。