← 返回题目列表

AtCoder · abc312_d

G. 计算括号序列

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给你一个非空字符串 S 组成 (, ),和 ?.
有 2^x 通过替换每个来获取新字符串的方法 ? in S 与 ( 和 ),其中 x 是出现的次数 ? in S。 其中,求数,取模 998244353,产生的方法 括号字符串.

如果满足以下条件之一,则称字符串为括号字符串。

  • 这是一个空字符串。
  • 这是一个串联 (, A,和 ),对于某些括号字符串 A.
  • 这是一个串联 A 和 B,对于一些非空括号字符串 A 和 B.

约束

  • S 是一个最大长度的非空字符串 3000 组成 (, ),和 ?.

输入

输入由标准输入按以下格式给出:

S

输出

打印答案。


示例输入 1

(???(?

示例输出 1

2

更换 S 与 ()()() or (())() 产生一个括号字符串。
其他替换不会产生括号字符串,因此 2 。


示例输入 2

)))))

示例输出 2

0

示例输入 3

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

示例输出 3

603032273

打印计数模数 998244353.