310004: CF1770G. Koxia and Bracket
Memory Limit：256 MB
Time Limit：5 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
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.Input
题意翻译
给定一个括号序列 $s$，你需要删除 **尽可能少** 的字符使得操作完的序列是个合法括号序列。 请求出所有最优删除方案的数量。$1\le |s|\le 5\times 10^5$，答案对 998244353 取模。 两种方案不同当且仅当存在一个位置在两种方案中一个被删除而另一个没有。Output
题目大意：
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平衡的唯一方式是删除唯一的字符，得到一个空的括号序列，这被认为是平衡的。
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平衡的唯一方式是删除唯一的字符，得到一个空的括号序列，这被认为是平衡的。