Count Bracket Sequences

题目描述

你得到一个非空字符串 $S$，它由 $($、$)$ 和 $?$ 组成。
通过将 $S$ 中的每个 $?$ 替换为 $($ 或 $)$，共有 $2^x$ 种得到新字符串的方式，其中 $x$ 是 $S$ 中 $?$ 的出现次数。在这些方式中，求生成一个括号串的方式数，对 $998244353$ 取模。 如果满足以下任一条件，则称该字符串为括号串。

它是空字符串。 它是 $($、$A$、和 $)$ 的串联，其中 $A$ 是某个括号串。 它是 $A$ 和 $B$ 的串联，其中 $A$ 和 $B$ 是非空括号串。

输入格式

输入从标准输入按以下格式给出： $S$

输出格式

输出答案。

(???(?

2

)))))

0

??????????????(????????(??????)?????????(?(??)

603032273

提示

$S$ 是一个非空字符串，长度最多为 $3000$，由 $($、$)$ 和 $?$ 组成。将 $S$ 替换为 $()()()$ 或 $(())()$ 会得到括号串。
其他替换不会得到括号串，所以应该打印 $2$。
对 $998244353$ 取结果的模。

标签: AtCoder|abc312D

来源

AtCoder|abc312D