103123: [Atcoder]ABC312 D - Count Bracket Sequences
Description
Score : $400$ points
Problem Statement
You are given a non-empty string $S$ consisting of (, ), and ?.
There are $2^x$ ways to obtain a new string by replacing each ? in $S$ with ( and ), where $x$ is the number of occurrences of ? in $S$. Among them, find the number, modulo $998244353$, of ways that yield a parenthesis string.
A string is said to be a parenthesis string if one of the following conditions is satisfied.
- It is an empty string.
- It is a concatenation of
(, $A$, and), for some parenthesis string $A$. - It is a concatenation of $A$ and $B$, for some non-empty parenthesis strings $A$ and $B$.
Constraints
- $S$ is a non-empty string of length at most $3000$ consisting of
(,), and?.
Input
The input is given from Standard Input in the following format:
$S$
Output
Print the answer.
Sample Input 1
(???(?
Sample Output 1
2
Replacing $S$ with ()()() or (())() yields a parenthesis string.
The other replacements do not yield a parenthesis string, so $2$ should be printed.
Sample Input 2
)))))
Sample Output 2
0
Sample Input 3
??????????????(????????(??????)?????????(?(??)
Sample Output 3
603032273
Print the count modulo $998244353$.
Input
Output
问题描述
给你一个包含 (, ), 和 ? 的非空字符串 $S$。
在 $S$ 中的每个 ? 上分别用 ( 和 ) 替换，共有 $2^x$ 种方式，其中 $x$ 是 $S$ 中 ? 出现的次数。在这些方式中，找出能形成 括号字符串 的方式的个数，对 $998244353$ 取模。
一个字符串被认为是括号字符串，如果满足以下条件之一。
- 它是空字符串。
- 它是
(, $A$, 和)$ 的拼接，其中 $A$ 是一个括号字符串。 - 它是 $A$ 和 $B$ 的拼接，其中 $A$ 和 $B$ 是非空括号字符串。
约束
- $S$ 是一个长度不超过 $3000$ 的非空字符串，由
(,), 和?组成。
输入
输入通过标准输入给出，格式如下：
$S$
输出
打印答案。
样例输入 1
(???(?
样例输出 1
2
将 $S$ 替换为 ()()() 或 (())() 可以形成括号字符串。
其他替换方式不能形成括号字符串，因此应该输出 $2$。
样例输入 2
)))))
样例输出 2
0
样例输入 3
??????????????(????????(??????)?????????(?(??)
样例输出 3
603032273
打印计数对 $998244353$ 取模后的结果。