CFCF2190B2.Sub-RBS (Hard Version)

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

本题为该问题的困难版本。不同版本间的差异在于：本版本需要计算 $s$ 的所有子序列的得分之和； $s$ 不一定是正则括号序列；同时对 $n$ 的约束条件更宽松。

我们称括号序列 $a$ 比括号序列 $b$ 更优，当且仅当满足以下任一条件：

$b$ 是 $a$ 的前缀，但 $a \ne b$ ；
设 $i$ 是 $a$ 和 $b$ 第一个出现字符不同的位置（若存在），且满足 $a_i = \texttt{(}$ 且 $b_i = \texttt{)}$ 。

对于任意括号序列 $t$ ，其得分定义如下：

若 $t$ 不是正则括号序列 $^{∗}$ ，则得分为 $0$ ；
若存在 $t$ 的一个正则括号子序列 $^{†}$ $r$ 满足 $r$ 比 $t$ 更优，则得分为所有此类子序列 $r$ 的长度 $|r|$ 的最大值；
否则，得分为 $0$ 。

换句话说， $t$ 的得分等于： $t$ 的所有“比 $t$ 更优”的正则括号子序列中，最长子序列的长度。若 $t$ 不是正则括号序列，或不存在比 $t$ 更优的正则子序列，则得分为 $0$ 。

给定一个长度为 $n$ 的括号序列 $s$ ，请计算 $s$ 的所有非空子序列的得分之和，并对 $998\,244\,353$ 取模。

$^{∗}$ 正则括号序列（Regular Bracket Sequence, RBS）的定义：将序列中原有字符间插入字符 $\texttt{1}$ 和 $\texttt{+}$ 后，能转化为合法算术表达式的括号序列。例如：

括号序列 $\texttt{()()}$ 和 $\texttt{(())}$ 是正则的（转化后的表达式分别为 $\texttt{(1)+(1)}$ 和 $\texttt{((1+1)+1)}$ ）；
括号序列 $\texttt{)(}$ 、 $\texttt{(}$ 和 $\texttt{)}$ 不是正则的。

$^{†}$ 子序列的定义：若序列 $a$ 可通过删除序列 $b$ 中任意位置的若干个（可能为 0 个或全部）元素得到，则称 $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$ 取模后的结果。

输入输出样例

输入#1

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

输出#1

说明/提示

第一个样例中，唯一的非空子序列是 $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$ ，因此总和为 $4$ 。

首页