Koxia and Bracket

题目描述

Chiyuu has a bracket sequence $ ^\dagger $ $ s $ of length $ n $ . Let $ k $ be the minimum number of characters that Chiyuu has to remove from $ s $ to make $ s $ balanced $ ^\ddagger $ . Now, Koxia wants you to count the number of ways to remove $ k $ characters from $ s $ so that $ s $ becomes balanced, modulo $ 998\,244\,353 $ . Note that two ways of removing characters are considered distinct if and only if the set of indices removed is different. $ ^\dagger $ A bracket sequence is a string containing only the characters "(" and ")". $ ^\ddagger $ A bracket sequence is called balanced if one can turn it into a valid math expression by adding characters + and 1. For example, sequences (())(), (), (()(())) and the empty string are balanced, while )(, ((), and (()))( are not.

输入输出格式

输入格式

The first line of input contains a string $ s $ ( $ 1 \leq |s| \leq 5 \cdot {10}^5 $ ) — the bracket sequence. It is guaranteed that $ s $ only contains the characters "(" and ")".

输出格式

Output a single integer — the number of ways to remove $ k $ characters from $ s $ so that $ s $ becomes balanced, modulo $ 998\,244\,353 $ .

输入输出样例

输入样例 #1

())(()

输出样例 #1

4

输入样例 #2

(

输出样例 #2

1

说明

In the first test case, it can be proved that the minimum number of characters that Chiyuu has to remove is $ 2 $ . There are $ 4 $ ways to remove $ 2 $ characters to make $ s $ balanced as follows. Deleted characters are noted as red. - $ \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{)} $ . In the second test case, the only way to make $ s $ balanced is by deleting the only character to get an empty bracket sequence, which is considered balanced.

题目大意：
Chiyuu有一个长度为n的括号序列s。设k为Chiyuu需要从s中删除的最少字符数，以使s平衡。现在，Koxia想要你计算删除k个字符使s平衡的方式数，对998,244,353取模。注意，只有当删除的索引集不同，两种删除字符的方式才被认为是不同的。

输入输出数据格式：
输入格式：
第一行输入包含一个字符串s（1≤|s|≤5×10^5）——括号序列。保证s只包含字符"("和")"。
输出格式：
输出一个整数——删除k个字符使s平衡的方式数，对998,244,353取模。

输入输出样例：
输入样例 #1
```
())(())
```
输出样例 #1
```
4
```
输入样例 #2
```
(
```
输出样例 #2
```
1
```

说明：
在第一个测试案例中，可以证明Chiyuu必须删除的最少字符数是2。有4种方式删除2个字符使s平衡，如下所示。删除的字符用红色标出。
- (红) ) (红( )
- ( ) 红) 红( (
- (红) ) (红( )
- ( ) 红) (红( )

在第二个测试案例中，使s平衡的唯一方式是删除唯一的字符，得到一个空的括号序列，这被认为是平衡的。题目大意： Chiyuu有一个长度为n的括号序列s。设k为Chiyuu需要从s中删除的最少字符数，以使s平衡。现在，Koxia想要你计算删除k个字符使s平衡的方式数，对998,244,353取模。注意，只有当删除的索引集不同，两种删除字符的方式才被认为是不同的。 输入输出数据格式： 输入格式： 第一行输入包含一个字符串s（1≤|s|≤5×10^5）——括号序列。保证s只包含字符"("和")"。 输出格式： 输出一个整数——删除k个字符使s平衡的方式数，对998,244,353取模。 输入输出样例： 输入样例 #1 ``` ())(()) ``` 输出样例 #1 ``` 4 ``` 输入样例 #2 ``` ( ``` 输出样例 #2 ``` 1 ``` 说明： 在第一个测试案例中，可以证明Chiyuu必须删除的最少字符数是2。有4种方式删除2个字符使s平衡，如下所示。删除的字符用红色标出。 - (红) ) (红( ) - ( ) 红) 红( ( - (红) ) (红( ) - ( ) 红) (红( ) 在第二个测试案例中，使s平衡的唯一方式是删除唯一的字符，得到一个空的括号序列，这被认为是平衡的。