← 返回题目列表

Codeforces · 1770/G

G. Koxia 和支架

中文机器翻译题面 查看原题

Chiyuu 有一个括号序列$$$^\dagger$$$ $$$s$$$,长度为$$$n$$$。令 $$$k$$$ 为 Chiyuu 必须从 $$$s$$$ 中删除以使 $$$s$$$ 平衡$$$^\ddagger$$$ 的最小字符数。

现在,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$$$ 为模。

示例

输入 #1

())(()

输出 #1

4

输入 #2

(

输出 #2

1

注意

在第一个测试用例中,可以证明Chiyuu 必须删除的最少字符数为$$$2$$$。有 $$$4$$$ 方法可以删除 $$$2$$$ 字符以使 $$$s$$$ 平衡,如下所示。删除的字符标记为红色。

- $$$\texttt{(} \color{红色}{\texttt{)}} \texttt{)} \color{红色}{\texttt{(}} \texttt{(} \texttt{)}$$$,
- $$$\texttt{(} \texttt{)} \color{红色}{\texttt{)}} \color{红色}{\texttt{(}} \texttt{(} \texttt{)}$$$,
- $$$\texttt{(} \color{红色}{\texttt{)}} \texttt{)} \texttt{(} \color{红色}{\texttt{(}} \texttt{)}$$$,
- $$$\texttt{(} \texttt{)} \color{红色}{\texttt{)}} \texttt{(} \color{红色}{\texttt{(}} \texttt{)}$$$。

在第二个测试用例中,使 $$$s$$$ 平衡的唯一方法是删除唯一的字符以获得空括号序列,这被认为是平衡的。