Znzryb's Blog
0%

Codeforces Round 1082 (Div. 2)-CF-1082-E. Rigged Bracket Sequence（括号串）（对括号串一个比较有用的工具就是这个把括号看成 1，-1，合法的括号串就是其前缀和时刻都不为负数，且最后为 0）

Posted on Edited on

题目大意

题目描述

给定一个长度为 nn 的合法括号序列 SS。

我们定义对 SS 的一个子序列进行向右循环移位操作：选中子序列所在的位置 i1,i2,…,iki_1, i_2, \dots, i_k，将这些位置上的字符同时更新为：

  • Si1←SikS_{i_1} \leftarrow S_{i_k}

  • Si2←Si1S_{i_2} \leftarrow S_{i_1}

  • Si3←Si2S_{i_3} \leftarrow S_{i_2}

  • …\dots

  • Sik←Sik−1S_{i_k} \leftarrow S_{i_{k-1}}

也就是说，选中的这些位置上的字符整体向右移动一位，最后一个字符移动到第一个被选中的位置。

例如，对于括号序列 ()(()())：

  • 若选中第 22 和第 44 个位置的字符（分别是 ) 和 (），移位后第 22 个位置变为 (，第 44 个位置变为 )，序列变成 ((())())。

  • 若选中第 22、33、55 个位置的字符（分别是 )、(、)），移位后第 22 个位置变为 )，第 33 个位置变为 )，第 55 个位置变为 (，序列变成 ())((())。

请计算有多少个非空子序列，使得在对其进行向右循环移位后，原序列 SS 仍然是一个合法的括号序列。由于答案可能很大，请输出其对 998244353998244353 取模的结果。

注：两个子序列如果选中的位置集合不同，则被认为是不同的子序列。

输入格式

第一行包含一个整数 tt（1≤t≤1041 \le t \le 10^4），表示测试用例的数量。
每个测试用例包含两行：

  • 第一行包含一个偶数 nn（2≤n≤3000002 \le n \le 300000），表示括号序列的长度。

  • 第二行包含一个长度为 nn 的合法括号序列 SS。
    保证所有测试用例中 nn 的总和不超过 300000300000。

输出格式

对于每个测试用例，在一行中输出一个整数，表示满足条件的非空子序列数量对 998244353998244353 取模的结果。

样例输入

1
2
3
4
5
6
7
8
9
4
2
()
4
()()
6
(()())
10
()((())())

样例输出

1
2
3
4
2
8
28
312

样例解释

对于第二个测试用例 ()()，以下 88 个非空子序列在向右移位后能使原序列保持合法：

  • 仅选中位置 11：移位后序列为 ()()

  • 仅选中位置 22：移位后序列为 ()()

  • 仅选中位置 33：移位后序列为 ()()

  • 仅选中位置 44：移位后序列为 ()()

  • 选中位置 11 和 33：移位后序列为 ()()

  • 选中位置 22 和 33：移位后序列为 (())

  • 选中位置 22 和 44：移位后序列为 ()()

  • 选中位置 11、22、33：移位后序列为 (())

image

这个就是所谓的right shift操作，那么其实就是向右循环移动一位。题目给你一个正规合法的括号串，问你在所有子序列当中，哪些子序列在进行了right shift操作以后还是合法的括号串（注意，子序列进行了right shift操作后，会反作用于原来的正规合法括号串，那么我们就是要看原来的正规合法括号串，在进行了这个操作以后是否还合法）。

思路讲解

对括号串一个比较有用的工具就是这个把括号看成 1，-1，合法的括号串就是其前缀和时刻都不为负数。（当然末尾必须是 0）

这样子我们就能够非常直观的看出，循环移动的影响范围只是从其第一个子序列的 id，到最后一个子序列的 id，其他的启示是不会影响的，因为对于他们的前缀和来说，包含的元素没有变化，和自然也没有变化。

有很多人觉得这道题目是 dp，认为是什么计数 DP 什么之类的，我觉得这个很难算是一个 DP, 或者说你如果你告诉一个比较拉的人，跟他讲这道题是 DP，他肯定是做不出来的，嗯，它更多的还是根据一个性质，然后去进行这么一个做法吧。

首先啊，我们使用前缀和工具不难得出这一结论：

image

然后我们就要想办法使用该结论进行计数。

哦，我们解释一下这个代码里面的各个东西吧。首先是这个 sum_dp 其实指的是这个包含 ）的这个答案数量。lans 计算出来就是这个所有包含这一位 ）的这个答案。

我们现在的目标，就是需要计算一下，如果要给下面一个 ） 用的话，合法的，只包含（ 的子序列有几个 ？这个数量就是 valid_no_right，那么，我们其实就是要知道，当前，没有 ）的子序列（当然是合法的），有多少个？实际上，要求出这个值，最好的方法就是从 lans 里面去求。lans 实际上是 i 自家带的兵，然后从所有的其他地方的兵转移过来的，那么这个其他地方的兵分为从带 ）的兵和不带这个的兵。那么 lans-sum_dp 是什么东西呢？这样子看，实际上很难看出来，我们不妨从目标下手，我们其实就是要把所有带 i 这个 ） 的给除掉。

那么 lans−sumdplans-sumdp 实际上其实就是：

lans←2i−1−upi−invalidCnt(lans−1)×sumdplans\gets 2^{i-1-upi-invalidCnt}\\(lans-1)\times sumdp

这里一大长串的2的次方实际上就是最初的 lans。那么这里的 lans-1 实际上是把只选了） 的情况给去掉，我们之所以会产生困惑，其实是我因为我们对 lans 有疑问，实际上 lans 是强制选取 i 的 ）的，所以排除只选 ） 的情况，只需要 -1 即可。

1
2
3
4
5
6
7
8
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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