CF-1073-D2. Sub-RBS (Hard Version)（注意虚拟节点可能的操作特判）（括号序列 dp 的状态设计） · znzryb
## 题目大意
### 1. 核心定义
- 括号序列比较 ("Better Than")：
对于两个括号序列 $a$ 和 $b$，满足以下条件之一则称 $a$ 比 $b$ “更好”：
1. $b$ 是 $a$ 的前缀，且 $a \neq b$。
1. 在第一个不相同的字符位置 $i$，$a_i = '('$ 且 $b_i = ')'$。
- **序列** $t$ **的得分 (Score)**：
1. 如果 $t$ 不是**正则括号序列** **(RBS)**，得分为 $0$。
1. 如果 $t$ 是 RBS，查找其所有的**正则括号子序列** $r$。如果存在某些 $r$ 满足 $r$ 比 $t$ “更好”，则得分为这些 $r$ 中长度 $|r|$ 的最大值。
1. 若不存在这样的 $r$，得分为 $0$。
### 2. 任务要求
给定一个长度为 $n$ ($1 \le n \le 100$) 的括号序列 $s$，求 $s$ 的所有**非空子序列**的得分之和，结果对 $998244353$ 取模。
---
### 3. 样例解释
- 样例 2：s = ()()()
考虑其中一个子序列 $t = "()()()"$：
- 它是一个 RBS。
- 它有一个子序列 $r = "(())"$（取原序列第 1, 3, 4, 6 位）。
- 比较 $t$ 和 $r$：第一位都是 `(`，第二位 $t_2 = ')'$ 而 $r_2 = '('$。根据定义，$r$ 比 $t$ 更好。
- $r$ 的长度为 $4$，经校验这是最长的更好子序列，故该子序列 $t$ 得分为 $4$。
- 其他子序列得分均为 $0$，总和为 $4$。
- **样例 3：****`s = (())()`**
- 对于子序列 $t = "(())()"$，虽然它是 RBS，但无法找到比它“更好”的 RBS 子序列。
- 例如，要在某位置 $i$ 更好，必须 $t_i = ')'$ 且 $r_i = '('$，但在该位置之前，$t$ 已经用完了所有的 `(` 匹配了前面的 `)`，无法构造出更优的正则子序列。
- 因此总和为 $0$。
## 思路讲解
首先，D1 当中，我们发现一个规律，就是只要 $s$ 串只要是有答案的，其答案就是 $|s|-2$，那么其有答案的条件是第一个 $)$ 出现的位置后，又至少出现了出现了两个 $($。
我们可以定义一个如下状态：
⚠️注意：这里的长度，个数，指的是合法方案个数及其合法方案的总（后缀）长度，这样子定义是为了方便记忆化搜索。
总体上的记忆化搜索过程可以描述为这样：
$$
\begin{aligned} & res \gets (0,0) \\ & \text{if } unbalance = 0 \land state = 3: res \gets (1,1) \\ & lres \gets \text{dfs}(idx, unbalance, state) \\ & \text{if } idx \neq 0: lres_{\text{len}} \gets lres_{\text{len}} + lres_{\text{num}} \\ & res \gets res + lres\end{aligned}
$$
那么之所以不在 $idx=0$ 的时候进行这个操作，是因为 0 是虚拟节点，没有实际字符。
```cpp
auto dfs=[&](auto && self,int idx,int unbalance,int state) -> Len_num{
if (unbalance<0) {
return {0,0};
}
if (vis[idx][unbalance][state]) {
return dp[idx][unbalance][state];
}
vis[idx][unbalance][state]=true;
// assert(idx<=N);
Len_num res={0,0};
if (unbalance==0 && state==3) {
// 相当于只选这个 s【idx】的时候
res={1,1};
}
for (int i=idx+1;i<=N;++i) {
Len_num lres;
if (s[i]==')') {
lres=self(self,i,unbalance-1,max(1,state));
}else {
int to_state;
if (state==0) to_state=0;
else to_state=min(3,state+1);
lres=self(self,i,unbalance+1,to_state);
}
res+=lres;
// 0 是一个虚拟节点，不会增加这个 res 长度
if (lres.len!=0 && idx!=0) {
// 这里给所有的方案增加一个长度，即选了
res.len+=lres.num;
}
res%=mod;
}
dp[idx][unbalance][state]=res;
return res;
};
Len_num res=dfs(dfs,0,0,0);
```
## AC代码
AC
[https://codeforces.com/contest/2191/submission/358546432](https://codeforces.com/contest/2191/submission/358546432)
::: 源代码
```cpp
/**
* Problem: D2. Sub-RBS (Hard Version)
* Contest: Codeforces Round 1073 (Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2191/problem/D2
* Created: 2026-01-18 01:00:44
* Author: Gospel_rock
*/
#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT;
/*
*
*/
struct Len_num {
ll len,num;
void operator+=(const Len_num &o) {
len+=o.len;
num+=o.num;
}
void operator%=(const ll a) {
len%=a;
num%=a;
}
};
void Solve() {
ll N;
cin >> N;
string s;
cin>>s;
s.insert(s.begin(),'#');
// dp 里面存的是合法方案数
vector dp(N+2,vector(N+2,vector<Len_num>(4)));
vector vis(N+2,vector(N+2,vector<char>(4)));
auto dfs=[&](auto && self,int idx,int unbalance,int state) -> Len_num{
if (unbalance<0) {
return {0,0};
}
if (vis[idx][unbalance][state]) {
return dp[idx][unbalance][state];
}
vis[idx][unbalance][state]=true;
// assert(idx<=N);
Len_num res={0,0};
if (unbalance==0 && state==3) {
// 相当于只选这个 s【idx】的时候
res={1,1};
}
for (int i=idx+1;i<=N;++i) {
Len_num lres;
if (s[i]==')') {
lres=self(self,i,unbalance-1,max(1,state));
}else {
int to_state;
if (state==0) to_state=0;
else to_state=min(3,state+1);
lres=self(self,i,unbalance+1,to_state);
}
res+=lres;
// 0 是一个虚拟节点，不会增加这个 res 长度
if (lres.len!=0 && idx!=0) {
res.len+=lres.num;
}
res%=mod;
}
dp[idx][unbalance][state]=res;
return res;
};
Len_num res=dfs(dfs,0,0,0);
ll ans=res.len-res.num*2;
ans%=mod;
if (ans<0) {
ans+=mod;
}
cout<<ans<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> lT;
while(lT--)
Solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2191/submission/358546432
1
1
(
1
6
()()()
*/
```
:::
## 心路历程（WA，TLE，MLE……）
$$
res\gets \{0,0\}\\
unbalance=0 \text{ and } state=3:res\gets \{1,1\}
\\
lres\gets \text{dfs}(idx,unbalance,state)\\
idx≠0:lres.len\gets lres.len+lres.num\\
res\gets res+lres
$$