题解：CF2201C Rigged Bracket Sequence
DoubleQLzn
·
·
题解
CF2201C
考虑将括号序列转化到序列 a 上，令左括号对应的值满足 a_i=1，右括号满足 a_i=-1，s_i=s_{i-1}+a_i，则序列合法的充要条件是：\forall i,s_i\geq 0 且 s_n=0。
右移 [i_1,i_2,\cdots,i_k] 带来的影响在于：对于 i_m\leq j<i_{m+1}，s_j\leftarrow s_j+a_{i_k}-a_{i_m}。
分类讨论：
考虑对第二种情况使用动态规划计数。f_i 表示钦定最后一位满足 a_{i_k}=-1 的合法方案数。
如果 f_j 可以转移到 f_i，分类讨论：
$a_j=-1$：全部点可以转移。
最后答案累加即可，对于 $a_i=1$ 的点计入 $2^{i-1}$，否则计入我们动态规划得出的 $f_i$。
#### Code
```cpp
#include <bits/stdc++.h>
using namespace std;
const int md = 998244353;
int dc = 1,n,p[300005],a[300005],s[300005],f[300005],g[300005],l[300005],r[300005];
namespace DoubleQLzn
{
void init()
{
return ;
}
void solve()
{
int lst = 0;
cin >> n;
p[0] = 1;
for (int i = 1;i <= n;i++)
{
char c;
cin >> c;
if (c == '(') a[i] = 1;
else a[i] = -1;
s[i] = s[i - 1] + a[i];
}
for (int i = 1;i <= n;i++) p[i] = p[i - 1] * 2 % md;
for (int i = 1;i <= n;i++)
{
int c;
if (i != lst) c = (l[i - 1] - l[lst] + md) % md;
else c = 0;
f[i] = (c + r[i - 1] + 1) % md;
if (a[i] == 1) l[i] = (l[i - 1] + f[i]) % md;
else l[i] = l[i - 1];
if (a[i] == -1) r[i] = (r[i - 1] + f[i]) % md;
else r[i] = r[i - 1];
// cout << c << ' ' << r[i - 1] << ' ' << f[i] << '\n';
if (s[i] <= 1) lst = i;
}
int ans = 0;
for (int i = 1;i <= n;i++) ans = (ans + (a[i] == 1 ? p[i - 1] : f[i])) % md;
cout << ans << '\n';
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
if (dc == 0) T = 1;
else cin >> T;
while (T--)
{
DoubleQLzn::init();
DoubleQLzn::solve();
}
return 0;
}
```