CF-1073-D2. Sub-RBS (Hard Version)（注意虚拟节点可能的操作特判）（括号序列 dp 的状态设计）

题目大意

1. 核心定义

• 括号序列比较 (“Better Than”)：
  对于两个括号序列 $a$ 和 $b$，满足以下条件之一则称 $a$ 比 $b$ “更好”：

  1. $b$ 是 $a$ 的前缀，且 $a \neq b$。
  2. 在第一个不相同的字符位置 $i$，$a_i = '('$ 且 $b_i = ')'$。

• 序列 $t$ 的得分 (Score)：

  1. 如果 $t$ 不是正则括号序列 (RBS)，得分为 $0$。
  2. 如果 $t$ 是 RBS，查找其所有的正则括号子序列 $r$。如果存在某些 $r$ 满足 $r$ 比 $t$ “更好”，则得分为这些 $r$ 中长度 $|r|$ 的最大值。
  3. 若不存在这样的 $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 是虚拟节点，没有实际字符。

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

源代码

/**
 * 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$$