CF1770G Koxia and Bracket

Chiyuu 有一个长度为 $n$ 的括号序列 $s$。令 $k$ 为 Chiyuu 需要从 $s$ 中删除的最少字符数，使得 $s$ 变为平衡括号序列。 现在，Koxia 想让你计算有多少种方法可以从 $s$ 中删除 $k$ 个字符，使得 $s$ 变为平衡括号序列。由于答案可能很大，请对 $998\,244\,353$ 取模。 注意，只有当删除字符的下标集合不同，才认为两种删除方式是不同的。 $^\dagger$ 括号序列是仅包含字符 "(" 和 ")" 的字符串。 $^\ddagger$ 如果一个括号序列可以通过添加字符 + 和 1 变成一个合法的数学表达式，则称其为平衡括号序列。例如，序列 (())()、()、((()())) 和空串是平衡的，而 )(、(()、和 (()))( 不是。

输入的第一行包含一个字符串 $s$（$1 \leq |s| \leq 5 \cdot 10^5$）——括号序列。 保证 $s$ 只包含字符 "(" 和 ")"。

输出一个整数，表示有多少种方法可以从 $s$ 中删除 $k$ 个字符，使得 $s$ 变为平衡括号序列。答案对 $998\,244\,353$ 取模。

在第一个测试用例中，可以证明 Chiyuu 需要删除的最少字符数为 $2$。有 $4$ 种方法可以删除 $2$ 个字符使 $s$ 变为平衡括号序列，具体如下。被删除的字符用红色标记。 - $\texttt{(} \color{Red}{\texttt{)}} \texttt{)} \color{Red}{\texttt{(}} \texttt{(} \texttt{)}$， - $\texttt{(} \texttt{)} \color{Red}{\texttt{)}} \color{Red}{\texttt{(}} \texttt{(} \texttt{)}$， - $\texttt{(} \color{Red}{\texttt{)}} \texttt{)} \texttt{(} \color{Red}{\texttt{(}} \texttt{)}$， - $\texttt{(} \texttt{)} \color{Red}{\texttt{)}} \texttt{(} \color{Red}{\texttt{(}} \texttt{)}$。 在第二个测试用例中，唯一的方法是删除唯一的字符，得到一个空括号序列，空串被认为是平衡的。 由 ChatGPT 4.1 翻译