Codeforces Round 1082 (Div. 2)-CF-1082-E. Rigged Bracket Sequence（括号串）（对括号串一个比较有用的工具就是这个把括号看成 1，-1，合法的括号串就是其前缀和时刻都不为负数，且最后为 0） · znzryb
## 题目大意
**题目描述**
给定一个长度为 $n$ 的合法括号序列 $S$。
我们定义对 $S$ 的一个子序列进行**向右循环移位**操作：选中子序列所在的位置 $i_1, i_2, \dots, i_k$，将这些位置上的字符同时更新为：
- $S_{i_1} \leftarrow S_{i_k}$
- $S_{i_2} \leftarrow S_{i_1}$
- $S_{i_3} \leftarrow S_{i_2}$
- $\dots$
- $S_{i_k} \leftarrow S_{i_{k-1}}$
也就是说，选中的这些位置上的字符整体向右移动一位，最后一个字符移动到第一个被选中的位置。
例如，对于括号序列 `()(()())`：
- 若选中第 $2$ 和第 $4$ 个位置的字符（分别是 `)` 和 `(`），移位后第 $2$ 个位置变为 `(`，第 $4$ 个位置变为 `)`，序列变成 `((())())`。
- 若选中第 $2$、$3$、$5$ 个位置的字符（分别是 `)`、`(`、`)`），移位后第 $2$ 个位置变为 `)`，第 $3$ 个位置变为 `)`，第 $5$ 个位置变为 `(`，序列变成 `())((())`。
请计算有多少个**非空**子序列，使得在对其进行向右循环移位后，原序列 $S$ 仍然是一个合法的括号序列。由于答案可能很大，请输出其对 $998244353$ 取模的结果。
注：两个子序列如果选中的位置集合不同，则被认为是不同的子序列。
**输入格式**
第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。
每个测试用例包含两行：
- 第一行包含一个偶数 $n$（$2 \le n \le 300000$），表示括号序列的长度。
- 第二行包含一个长度为 $n$ 的合法括号序列 $S$。
保证所有测试用例中 $n$ 的总和不超过 $300000$。
**输出格式**
对于每个测试用例，在一行中输出一个整数，表示满足条件的非空子序列数量对 $998244353$ 取模的结果。
**样例输入**
```
4
2
()
4
()()
6
(()())
10
()((())())
```
**样例输出**
```
2
8
28
312
```
**样例解释**
对于第二个测试用例 `()()`，以下 $8$ 个非空子序列在向右移位后能使原序列保持合法：
- 仅选中位置 $1$：移位后序列为 `()()`
- 仅选中位置 $2$：移位后序列为 `()()`
- 仅选中位置 $3$：移位后序列为 `()()`
- 仅选中位置 $4$：移位后序列为 `()()`
- 选中位置 $1$ 和 $3$：移位后序列为 `()()`
- 选中位置 $2$ 和 $3$：移位后序列为 `(())`
- 选中位置 $2$ 和 $4$：移位后序列为 `()()`
- 选中位置 $1$、$2$、$3$：移位后序列为 `(())`
这个就是所谓的right shift操作，那么其实就是向右循环移动一位。题目给你一个正规合法的括号串，问你在所有子序列当中，哪些子序列在进行了right shift操作以后还是合法的括号串（注意，子序列进行了right shift操作后，会反作用于原来的正规合法括号串，那么我们就是要看原来的正规合法括号串，在进行了这个操作以后是否还合法）。
## 思路讲解
::: 猜测 dp，但是不满足合法 → 合法转移
这种题目，先猜一手 dp。
[CF-1073-D2. Sub-RBS (Hard Version)（注意虚拟节点可能的操作特判）（括号序列 dp 的状态设计）](/2026/01/17/20260117-15aaa729)
这道题目使用了不平衡度作为 dp 的状态设计，不知道这个对我们有没有什么启示？
这提示我们可能不是 dp。
:::
::: 探路：猜测
我们容易写出如下程序。
```cpp
for (int i=1;i<=N;++i) {
if (s[i]=='(') {
// 这个分支应该是没有什么问题
// 因为这计数已经是顶格了，而且往前移动左括号，绝对是保险的
ans+=binpow(2,i-1);
ans%=mod;
}else {
// 一样的，移动起来肯定没问题
cnt_right++;
ans+=binpow(2,cnt_right-1);
ans%=mod;
}
}
```
:::
**对括号串一个比较有用的工具就是这个把括号看成 1，-1，合法的括号串就是其前缀和时刻都不为负数**。（当然末尾必须是 0）
这样子我们就能够非常直观的看出，循环移动的影响范围只是从其第一个子序列的 id，到最后一个子序列的 id，其他的启示是不会影响的，因为对于他们的前缀和来说，包含的元素没有变化，和自然也没有变化。
::: 除了等效第一位和第一位以外，还有其他不能选的情况
好的，我仔细读完了你的程序。让我先总结你的做法，然后回答你的问题。
**你的做法理解**
1. **末尾是** **`(`** **的子序列**：直接贡献 $2^{i-1}$，因为最后一位是 `(` 时循环移位只会让前缀和增加或不变，恒合法。这部分没问题。
1. **末尾是** **`)`** **且不是最后一位** $N$：你认为"不能选的位置"只有**等效第一位**——即 `(` 且 `pre_sum = 1` 的位置（前面所有括号都匹配完了）。排除这些后，其余位置自由选取，贡献 $2^{i-1-\text{equal\_st\_cnt}}$。
1. **末尾是最后一位** $N$：特殊处理，加上 `ans_else`。
**你的核心猜想是：对于末尾是** **`)`** **的子序列，只需要排除"等效第一位"（****`pre_sum = 1`** **的** **`(`****），其他位置都可以自由选取。**
---
**答案是：除了等效第一位以外，确实还有其他不能选的情况。**
反例：$S = $ `(())()` （长度 6）
```
位置: 1 2 3 4 5 6
字符: ( ( ) ) ( )
pre_sum: 1 2 1 0 1 0
```
考虑子序列 $\{2, 4\}$，即选中位置 2 的 `(` 和位置 4 的 `)`。
- 位置 2 的 `(` 的 `pre_sum = 2`，**不是等效第一位**，你的算法不会排除它。
- 但移位后：$S_2 \leftarrow S_4 = )$，$S_4 \leftarrow S_2 = ($。
- 新序列：`(` `)` `)` `(` `(` `)` = `())((`）`
- 前缀和：$0, 1, 0, -1$ —— 出现负数，**不合法**。
所以 $\{2, 4\}$ 是无效的，但你的算法把它算进去了。
**根本原因**：位置 2 是 `(` 且 `pre_sum = 2`，它本身看起来"够高"。但从位置 2 到下一个选中位置 4 之间，`pre_sum` 经过了位置 3 的值 1，低于 2。根据正确的条件，选中一个 `(` 后，**从该位置到下一个选中位置之间，前缀和必须始终** $\ge 2$。位置 3 的前缀和是 1，违反了这个条件。
**总结规律**：一个 `(` 位置 $j$ 能否被安全选入子序列，不仅取决于 $P(j)$ 本身，还取决于**从** $j$ **到下一个被选位置之间，前缀和是否一直** $\ge 2$。这是一个和"下一个选了谁"相关的动态条件，无法简单地通过排除固定的位置集合来处理。等效第一位（$P = 1$ 的 `(`）只是最极端的情况——它们在 $P(j) = 1 < 2$ 处立刻就违反条件，所以**无论如何都不能选**。但 $P(j) = 2$ 的 `(` 也可能不能选，取决于后面前缀和是否会掉到 2 以下。
:::
::: AI 对我得出的新结论的认可（现在的问题是如何用该结论进行计数）
当然这里的结论都是对这个最后一个是 `)` 的情况来讲。
你的意思我理解了：
**你的规则**：在所选子序列的元素中，如果出现形如 `(((...)` 的模式——即一段连续的（子序列意义上的）`(` 后面跟着一个 `)`，设第一个 `(` 在原串中的位置为 $l$，`)` 的位置为 $r$，那么原串在 $[l, r]$ 区间内不允许出现 `pre_sum` $\le 1$ 的位置。
**初步结论：这个规则是正确的**（在子序列末尾元素是 `)` 的前提下）。
精确来说，约束区间应该是 $[l, r-1]$ 而非 $[l, r]$（因为位置 $r$ 是下一个被选中的位置，约束范围到 $r-1$ 为止），但差别不大，用 $[l, r]$ 只是稍微更严格一点点。
**原因**：子序列中每个被选的 `(` 到它在子序列中的下一个被选位置之间，前缀和必须 $\ge 2$。一段连续的 `(((` 加上一个 `)` 形成的块，由 telescoping 可得，约束等价于从第一个 `(` 到 `)` 之前，前缀和都 $\ge 2$。
用你之前的反例验证：$S = $ `(())()` 中子序列 $\{2, 4\}$，这是一个 `()` 块，$l=2, r=4$，而 $P(3) = 1 \le 1$，违反规则，确实非法。
不过要注意：这个规则虽然正确，但它是**上下文相关**的——同一个 `(` 位置，如果下一个选中的是近处的 `)`（中间前缀和都 $\ge 2$），就合法；如果下一个选中的是远处的 `)`（中间前缀和掉到了 $1$），就非法。所以没法简单地把某些位置标记为"不可选"，这也是为什么需要用递推/DP 来追踪状态。
:::
::: WA，没有对 ）的选与不选进行判断
```cpp
_______________[ Sample Testcase #1 INPUT ]_______________
4
2
()
4
()()
6
(()())
10
()((())())
_______________[ Sample Testcase #1 OUTPUT]_______________
2
8
28
276
```
```cpp
}else {
// 其实和等效第一位，第一位都没什么关系
// 具体来讲，应该是：在所选子序列的元素中，如果出现形如 (((...) 的模式——即一段连续的（子序列意义上的）( 后面跟着一个 )，设第一个 '(' 在原串中的位置为 $l$，')' 的位置为 $r$，那么原串在 $[l, r)$ 区间内不允许出现 pre_sum $\le 1$ 的位置。
// 这里不需要分这个 i 是 N 和不是 N 的情况，因为实际上来说，最后一个地方的前缀和一定是 0
// 如果最后是 ( ，那么前缀和为负数的情况一定更早爆发了
ll lans=binpow(2,i-1-up_i-invalid_cnt);
lans*=sum_dp;
lans%=mod;
sum_dp+=lans;
sum_dp%=mod;
ans+=lans;
ans%=mod;
up_i=i;
invalid_cnt=0;
}
```
下面这个 ai 讲的太复杂了，**其实就是我的代码要选择前面一段的** **`(`** **话，一定会选前面一段的** **`)`**，但这个显然是不对的。**但是什么时候都可以抛弃 ）吗？**显然也不是。什么时候？其实就是**当 ）的这个 presum>1 的时候才可以跨段**。
好，我用第四个样例 $S = $ `()((())())` 给一个具体的被遗漏的子序列。
```
位置: 1 2 3 4 5 6 7 8 9 10
字符: ( ) ( ( ( ) ) ( ) )
pre_sum: 1 0 1 2 3 2 1 2 1 0
```
你的算法按 `)` 位置分段：段 [0,2]、段 [2,6]、段 [6,7]、段 [7,9]、段 [9,10]。
考虑子序列 **{4, 7}**——选位置 4 的 `(` 和位置 7 的 `)`。
验证合法性：移位后 $S_4 \leftarrow S_7 = )$，$S_7 \leftarrow S_4 = ($，新序列：
```
原始: ( ) ( ( ( ) ) ( ) )
新的: ( ) ( ) ( ) ( ( ) ) = "()()()(())"
```
前缀和 0,1,0,1,0,1,0,1,2,1,0，全部非负，**合法**。
**但你的算法漏掉了它。** 原因：
- 位置 4 在**段 [2,6]** 里，位置 7 在**段 [6,7]** 里。
- 处理段 [2,6] 时（到达位置 6 的 `)`），`lans = 8` 计入了 `sum_dp`。这 8 个子序列都是**以位置 6 结尾**的。
- 但子集 {4} 是**没有选位置 6** 的——它选了 `(` 在位置 4，一直到位置 6 都没遇到被选的 `)`，约束还"悬着"。
- 到了段 [6,7]，处理位置 7 时，你用 `lans = 2^0 × sum_dp = 10`。这 10 只包含"已经没有活跃约束"的子集。子集 {4} 这种"约束还悬着"的，不在 `sum_dp` 里，所以 {4,7} 就漏了。
这就是"跨段延续"的意思：位置 4 的 `(` 在段 [2,6] 里被选中，但它的约束没有在段 [2,6] 的 `)` 处被消解（因为没选位置 6），而是**跨过了位置 6，延续到了段 [6,7]**，在位置 7 的 `)` 处才被消解。你的 `sum_dp` 没追踪这些"悬而未决"的子集，所以漏计了。
加 `f1` 之后，`f1 = 6` 恰好追踪了这 6 个悬而未决的子集：{4}、{5}、{2,4}、{2,5}、{4,5}、{2,4,5}。它们加上位置 7 就构成 6 个被遗漏的合法子序列。
:::
有很多人觉得这道题目是 dp，认为是什么计数 DP 什么之类的，我觉得这个很难算是一个 DP, 或者说你如果你告诉一个比较拉的人，跟他讲这道题是 DP，他肯定是做不出来的，嗯，它更多的还是根据一个性质，然后去进行这么一个做法吧。
首先啊，我们使用前缀和工具不难得出这一结论：
然后我们就要想办法使用该结论进行计数。
哦，我们解释一下这个代码里面的各个东西吧。首先是这个 sum_dp 其实指的是这个包含 ）的这个答案数量。lans 计算出来就是这个所有包含这一位 ）的这个答案。
我们现在的目标，就是需要计算一下，如果要给下面一个 `）` 用的话，**合法的，只包含（ 的子序列有几个** ？这个数量就是 valid_no_right，那么，我们其实就是要知道，当前，没有 `）`的子序列（当然是合法的），有多少个？实际上，要求出这个值，最好的方法就是从 lans 里面去求。lans 实际上是 i 自家带的兵，然后从所有的其他地方的兵转移过来的，那么这个其他地方的兵分为从带 `）`的兵和不带这个的兵。那么 lans-sum_dp 是什么东西呢？这样子看，实际上很难看出来，我们不妨从目标下手，**我们其实就是要把所有带 i 这个** **`）`** **的给除掉**。
那么 $lans-sumdp$ 实际上其实就是：
$$
lans\gets 2^{i-1-upi-invalidCnt}\\(lans-1)\times sumdp
$$
这里一大长串的2的次方实际上就是最初的 lans。那么这里的 lans-1 实际上是把只选了`）` 的情况给去掉，我们之所以会产生困惑，其实是我因为我们对 lans 有疑问，实际上 lans 是强制选取 i 的 `）`的，所以排除只选 `）` 的情况，只需要 -1 即可。
```cpp
ll lans=binpow(2,i-1-up_i-invalid_cnt);
lans*=(sum_dp+valid_no_right);
lans%=mod;
if (pre_sum[i]>1) {
valid_no_right=lans-sum_dp;
}else {
valid_no_right=0;
}
```
```cpp
for (int i=1;i<=N;++i) {
if (s[i]=='(') {
// 这个分支应该是没有什么问题
// 因为这计数已经是顶格了，而且往前移动左括号，绝对是保险的
ans+=binpow(2,i-1);
ans%=mod;
if (pre_sum[i]<=1) {
invalid_cnt++;
}
}else {
// 其实和等效第一位，第一位都没什么关系
// 具体来讲，应该是：在所选子序列的元素中，如果出现形如 (((...) 的模式——即一段连续的（子序列意义上的）( 后面跟着一个 )，设第一个 '(' 在原串中的位置为 l，')' 的位置为 $r$，那么原串在 [l, r) 区间内不允许出现 pre_sum ≤ 1 的位置。
// 这里不需要分这个 i 是 N 和不是 N 的情况，因为实际上来说，最后一个地方的前缀和一定是 0
// 如果最后是 ( ，那么前缀和为负数的情况一定更早爆发了
ll lans=binpow(2,i-1-up_i-invalid_cnt);
lans*=(sum_dp+valid_no_right);
lans%=mod;
if (pre_sum[i]>1) {
valid_no_right=lans-sum_dp;
}else {
valid_no_right=0;
}
sum_dp+=lans;
sum_dp%=mod;
ans+=lans;
ans%=mod;
up_i=i;
invalid_cnt=0;
}
}
```
## AC代码
AC
[https://codeforces.com/contest/2202/submission/364279343](https://codeforces.com/contest/2202/submission/364279343)
::: 源代码
```cpp
/**
* Problem: E. Rigged Bracket Sequence
* Contest: Codeforces Round 1082 (Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2202/problem/E
* Created: 2026-02-24 16:05:48
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#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 debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\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 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,testcase;
/*
*
*/
// 在 k<=0 的时候返回 1
ll binpow(ll a,ll k,const ll &p=mod){
ll res=1;
a%=p;
while(k>0){
if((k&1)==1) res=a*res%p;
a=a*a%p;
k>>=1;
}
return res;
}
void Solve() {
ll N;
cin >> N;
string s;
cin >> s;
s.insert(s.begin(),'#');
// 感觉也不一定是 dp
// 可能是这个观察
ll ans=0;
ll cnt_right=0;
vector<ll> pre_sum(N+2);
for (int i=1;i<=N;++i) {
pre_sum[i]=pre_sum[i-1]+(s[i]=='('?1:-1);
}
ll invalid_cnt=0;
// vector<ll> dp;
ll sum_dp=1;
ll up_i=0;
ll valid_no_right=0;
for (int i=1;i<=N;++i) {
if (s[i]=='(') {
// 这个分支应该是没有什么问题
// 因为这计数已经是顶格了，而且往前移动左括号，绝对是保险的
ans+=binpow(2,i-1);
ans%=mod;
if (pre_sum[i]<=1) {
invalid_cnt++;
}
}else {
// 其实和等效第一位，第一位都没什么关系
// 具体来讲，应该是：在所选子序列的元素中，如果出现形如 (((...) 的模式——即一段连续的（子序列意义上的）( 后面跟着一个 )，设第一个 '(' 在原串中的位置为 $l$，')' 的位置为 $r$，那么原串在 $[l, r)$ 区间内不允许出现 pre_sum $\le 1$ 的位置。
// 这里不需要分这个 i 是 N 和不是 N 的情况，因为实际上来说，最后一个地方的前缀和一定是 0
// 如果最后是 ( ，那么前缀和为负数的情况一定更早爆发了
ll lans=binpow(2,i-1-up_i-invalid_cnt);
lans*=(sum_dp+valid_no_right);
lans%=mod;
if (pre_sum[i]>1) {
valid_no_right=lans-sum_dp;
}else {
valid_no_right=0;
}
sum_dp+=lans;
sum_dp%=mod;
ans+=lans;
ans%=mod;
up_i=i;
invalid_cnt=0;
}
}
ans%=mod;
if (ans<0) ans+=mod;
cout<<ans<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2202/submission/364279343
1
4
()()
1
10
()((())())
if (i!=N) {
// if (dp.empty()) {
// ll lans=binpow(2,i-1-sum_gt_1_cnt);
// dp.push_back(lans);
// sum_dp+=lans;
// }else {
// }
}else {
// 这里本来是想要减的，但是实际上减了 1，还要再+1
// sum_dp--;
ll lans=binpow(2,i-1-up_i-invalid_cnt);
lans*=sum_dp;
lans%=mod;
sum_dp+=lans;
sum_dp%=mod;
ans+=lans;
ans%=mod;
}
// 我感觉只要不要选到非常明显的，比如最后一位是(，第一位是)这种，其他都是合法的？
// 我们试一试
if (i!=N) {
// 不能够选这个第一位
// 其实我们不能选的是所有的等效第一位。
// 什么是等效第一位？就是前面的左括号都匹配掉了，这不是就是和第一位一样了？也就是他这位的前缀和为 1。
ll lans=binpow(2,i-1-equal_st_cnt);
ans+=lans;
ans_else+=lans;
ans_else%=mod;
ans%=mod;
}else {
// i=N 的稍微有点烦，我们需要想一想
// 我们应该是在不能选等效第一位的基础上
// 我们紧靠着 ) 的还不能是 (，否则就不合法了。
ans+=ans_else;
ans++;
}
// 一样的，移动起来肯定没问题
// cnt_right++;
// ans+=binpow(2,cnt_right-1);
// ans%=mod;
// 以 i 为结尾的，所有子序列当中，合法的有多少？
// 先这样子定义试试。因为看这道题目的这个数据范围，我们没有多少选择。
vector<ll> dp(N+2);
for (int i=1;i<=N;++i) {
dp[i]=
}
ll ans=0;
for (int i=1;i<=N;++i) {
ans+=dp[i];
ans%=mod;
}
cout<<ans<<"\n";
*/
```
:::