A6954. abc312D-括号序列计数
编程题
普及/提高-
知识点
题目描述
给你一个由
有 $2^x$ 种方法可以将 $S$ 中的每个
如果满足以下条件之一，则称该字符串为括号字符串。
- 是空字符串。
- 对于某个括号字符串 $A$ 而言，它是
- 对于某个非空括号字符串 $A$ 和 $B$ 而言，它是 $A$ 和 $B$ 的连接。
(,)和 ?组成的非空字符串 $S$ 。 有 $2^x$ 种方法可以将 $S$ 中的每个
? 替换为 (和)，从而得到一个新的字符串，其中 $x$ 是 $S$ 中 ? 出现的次数。请找出在 $998244353$ 的模数中，有多少种方法能得到**括弧字符串**。如果满足以下条件之一，则称该字符串为括号字符串。
- 是空字符串。
- 对于某个括号字符串 $A$ 而言，它是
(、 $A$ 和 )的连接。- 对于某个非空括号字符串 $A$ 和 $B$ 而言，它是 $A$ 和 $B$ 的连接。
输入格式
输入内容由标准输入法提供，格式如下
```
$S$
```
#### 限制因素
- $S$ 是一个长度不超过 $3000$ 的非空字符串，由
```
$S$
```
#### 限制因素
- $S$ 是一个长度不超过 $3000$ 的非空字符串，由
(,)和 ?组成。输出格式
打印答案。
输入输出样例
输入 #1
(???(?
输出 #1
2
说明/提示
对于样例1
用
其他替换不会产生括号字符串，因此应打印 $2$ 。
用
()()()或(())()替换 $S$ 得到一个括号字符串。 其他替换不会产生括号字符串，因此应打印 $2$ 。