← 返回题目列表

Codeforces · 2190/B2

B2. 子RBS(硬版)

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

这是问题的困难版本。版本之间的区别在于,在这个版本中,您需要找到$$$s$$$的所有子序列的分数总和; $$$s$$$ 不一定是 常规括号序列,并且 $$$n$$$ 的约束较低.

我们说括号序列 $$$a$$$ 是 更好 比括号序列 $$$b$$$ 如果满足以下条件之一:

  • $$$b$$$ 是 $$$a$$$ 的前缀,但 $$$a \ne b$$$;或
  • 设 $$$i$$$ 为 $$$a_i \neq b_i$$$ 的第一个位置(如果存在),然后是 $$$\color{red}{a_i = \texttt{(}}$$$ 和 $$$\color{red}{b_i = \texttt{)}}$$$。

对于任意括号序列$$$t$$$,我们定义它的 分数 的方式如下:

  • 如果 $$$t$$$ 是 不 a 常规括号序列$$$^{\text{*}}$$$,得分为$$$0$$$。
  • 如果 $$$t$$$ 存在正则括号子序列 $$$^{\text{†}}$$$ $$$r$$$ 使得 $$$r$$$ 为 更好 大于 $$$t$$$,则得分等于所有此类子序列 $$$r$$$ 上 $$$|r|$$$ 的最大值。
  • 否则,得分为 $$$0$$$。

换句话说,$$$t$$$的分数是$$$t$$$的最长正则括号子序列的长度,它比$$$t$$$更好。如果 $$$t$$$ 不是正则括号序列,或者不存在比 $$$t$$$ 更好的正则子序列,则得分为 $$$0$$$。

给你一个括号序列$$$s$$$,长度为$$$n$$$。求 $$$s$$$ 模 $$$998\,244\,353$$$ 的所有非空子序列的分数总和。

$$$^{\text{*}}$$$A 常规括号序列 是一个括号序列,通过在序列的原始字符之间插入字符 $$$\texttt{1}$$$ 和 $$$\texttt{+}$$$ 可以将其转换为正确的算术表达式。例如:

  • 括号序列 $$$\texttt{()()}$$$ 和 $$$\texttt{(())}$$$ 是正则表达式(结果表达式为 $$$\texttt{(1)+(1)}$$$ 和 $$$\texttt{((1+1)+1)}$$$);
  • 括号序列 $$$\texttt{)(}$$$、$$$\texttt{(}$$$ 和 $$$\texttt{)}$$$ 不是。

$$$^{\text{†}}$$$ 序列 $$$a$$$ 是序列 $$$b$$$ 的子序列,如果 $$$a$$$ 可以通过从任意位置删除多个(可能是零个或全部)元素从 $$$b$$$ 获得。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 30$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 字符串 $$$s$$$ 的长度。

每个测试用例的第二行包含一个长度为 $$$n$$$ 的序列 $$$s$$$,仅由字符 $$$\texttt{(}$$$ 和 $$$\texttt{)}$$$ 组成。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$100$$$。

输出

对于每个测试用例,打印一个整数 - $$$s$$$ 的所有子序列的分数总和,以 $$$998\,244\,353$$$ 为模。

示例

输入
复制

5
1
(
6
()()()
6
(())()
8
(())()()
22
()()())()()(()()()((()

输出
复制

0
4
0
22
563070

注意

在第一个示例中,唯一的非空子序列是 $$$g = \texttt{(}$$$。它不是 常规括号序列,所以它的分数是$$$0$$$,总和也是$$$0$$$。

在第二个示例中,考虑 $$$g = s = \texttt{()()()}$$$。它是一个 常规括号序列。我们可以选择 $$$r = \texttt{(())}$$$,它是 $$$g$$$ 的子序列。 $$$r$$$ 和 $$$g$$$ 不同的第一个索引是 $$$i = 2$$$。由于 $$$r_2 = \texttt{(}$$$ 和 $$$g_2 = \texttt{)}$$$,$$$r$$$ 优于 $$$g$$$。因此,$$$g$$$ 的分数为$$$|r| = 4$$$。 $$$s$$$ 的所有其他非空子序列的分数等于 $$$0$$$。