526互联

洛谷P7914 [CSP-S 2021] 括号序列

发布时间 2023-06-21 20:11:15作者: cztq

主要参考：洛谷题解

[CSP-S 2021] 括号序列

题目描述

小 w 在赛场上遇到了这样一个题：一个长度为 \(n\) 且符合规范的括号序列，其有些位置已经确定了，有些位置尚未确定，求这样的括号序列一共有多少个。

身经百战的小 w 当然一眼就秒了这题，不仅如此，他还觉得一场正式比赛出这么简单的模板题也太小儿科了，于是他把这题进行了加强之后顺手扔给了小 c。

具体而言，小 w 定义“超级括号序列”是由字符 (、)、* 组成的字符串，并且对于某个给定的常数 \(k\)，给出了“符合规范的超级括号序列”的定义如下：

  1. ()、(S) 均是符合规范的超级括号序列，其中 S 表示任意一个仅由不超过 \(\bm{k}\) 个字符 * 组成的非空字符串（以下两条规则中的 S 均为此含义）；
  2. 如果字符串 A 和 B 均为符合规范的超级括号序列，那么字符串 AB、ASB 均为符合规范的超级括号序列，其中 AB 表示把字符串 A 和字符串 B 拼接在一起形成的字符串；
  3. 如果字符串 A 为符合规范的超级括号序列，那么字符串 (A)、(SA)、(AS) 均为符合规范的超级括号序列。
  4. 所有符合规范的超级括号序列均可通过上述 3 条规则得到。

例如，若 \(k = 3\)，则字符串 ((**()*(*))*)(***) 是符合规范的超级括号序列，但字符串 *()、(*()*)、((**))*)、(****(*)) 均不是。特别地，空字符串也不被视为符合规范的超级括号序列。

现在给出一个长度为 \(n\) 的超级括号序列，其中有一些位置的字符已经确定，另外一些位置的字符尚未确定（用 ? 表示）。小 w 希望能计算出：有多少种将所有尚未确定的字符一一确定的方法，使得得到的字符串是一个符合规范的超级括号序列？

可怜的小 c 并不会做这道题，于是只好请求你来帮忙。

输入格式

第一行，两个正整数 \(n, k\)。

第二行，一个长度为 \(n\) 且仅由 (、)、*、? 构成的字符串 \(S\)。

输出格式

输出一个非负整数表示答案对 \({10}^9 + 7\) 取模的结果。

样例 #1

样例输入 #1

7 3
(*??*??

样例输出 #1

5

样例 #2

样例输入 #2

10 2
???(*??(?)

样例输出 #2

19

样例 #3

样例输入 #3

见附件中的 bracket/bracket3.in

样例输出 #3

见附件中的 bracket/bracket3.ans

样例 #4

样例输入 #4

见附件中的 bracket/bracket4.in

样例输出 #4

见附件中的 bracket/bracket4.ans

提示

【样例解释 #1】

如下几种方案是符合规范的：

(**)*()
(**(*))
(*(**))
(*)**()
(*)(**)

【数据范围】

测试点编号 \(n \le\) 特殊性质
\(1 \sim 3\) \(15\) 无
\(4 \sim 8\) \(40\) 无
\(9 \sim 13\) \(100\) 无
\(14 \sim 15\) \(500\) \(S\) 串中仅含有字符 ?
\(16 \sim 20\) \(500\) 无

对于 \(100 \%\) 的数据，\(1 \le k \le n \le 500\)。

题解

那篇题解中已经说得十分清楚了，但不过对于部分转移来说，明显不够优秀，还有可优化之处

主要更改

优化了 \(dp_{l,r,4}\) 的状态转移，并且去除了 \(dp_{l,r,5}\)，增加了对于初始化的说明

正文

首先肯定是区间 \(dp\)，令 \(dp_{i,j}\) 表示从位置 \(i\) 到位置 \(j\) 一共的合法序列总情况数量。

但是不同的形态可能会有不同的转移，如：(S)这种只能从S转移过来等等。所以只开两维的 \(dp\) 状态必然是不够的。

直接将方法吧。将两位的 \(dp\) 扩充为三维，第三位表示不同的形态种类，\(dp\) 状态就变成了 \(dp_{i,j,[0,4]}\)。每种状态表示：

  • \(dp_{i,j,0}\): 形态如***...*的括号序列（即全部是*）。
  • \(dp_{i,j,1}\): 形态如(...)的括号序列（即左右直接被括号包裹且最左边括号与最右边的括号相互匹配）。
  • \(dp_{i,j,2}\): 形态如(...)**(...)***的括号序列（即左边以括号序列开头，右边以*结尾）。
  • \(dp_{i,j,3}\): 形态如(...)***(...)*(...)的括号序列（即左边以括号序列开头，右边以括号序列结尾，注意：第2种形态也属于这种形态）。
  • \(dp_{i,j,4}\): 形态如***(...)**(...)的括号序列（即左边以*开头，右边以括号序列结尾）。

设定完状态以后，转移就直接出来了，注意：为了防止连续超过 \(k\) 个*一起出现，转移的时候不能把两段*拼接起来，在状态 \(1\) 的时候暴力判断一下两端的距离是否是 \(\le k\) 的，是的才能转移。

作为一篇题解，转移虽然很简单，但是好得说一下吧。

  • \(dp_{l,r,0}\)（直接特判）
    • 没什么好解释的
  • \(dp_{l,r,1}=(dp_{l+1,r-1,0}+dp_{l+1,r-1,2}+dp_{l+1,r-1,3}+dp_{l+1,r-1,4}) \times compare(l,r)\)
    • \(compare(i,j)\) 表示第 \(i\) 位与第 \(j\) 位能否配对成括号，能则为 \(1\)，否则为 \(0\)。
    • 加括号时，里面可以是全*，可以是有一边是*，也可以是两边都不是*，唯独不能两边都是*且中间有括号序列。
  • \(dp_{l,r,2}=\sum\limits_{i=l}^{r-1} dp_{l,i,3}\times dp_{i+1,r,0}\)
    • 左边以括号序列开头且以括号序列结尾的是第3种，右边接一串*，是第0种。
  • \(dp_{l,r,3}=\sum\limits_{i=l}^{r-1} (dp_{l,i,2}+dp_{l,i,3})\times dp_{i+1,r,1}+dp_{l,r,1}\)
    • 左边以括号序列开头，结尾随便，符合的有第 \(2\) 和第 \(3\) 种，右边接一个括号序列，是第 \(1\) 种。
    • 记得加上直接一个括号序列的。
  • \(dp_{l,r,4}=\sum\limits_{i=l}^{r-1} dp_{l,i,0}\times dp_{i+1,r,3}\)
    • 从定义就十分容易看出第 \(4\) 种是第 \(2\) 种反过来的情况，便可以用第 \(2\) 种的式子将 \(0\) 与 \(3\)交换后得到

最后，答案必须以括号序列开头，以括号序列结尾，所以直接是 \(dp_{1,n,3}\)。

这样，初始状态也就没什么问题了，对于所有的 \(i\) 满足 \(1\le i \le n\)，有 \(dp_{i,i-1,0}=1\) 。

对于初始化的问题，可以从对 \(dp_{l,r,1}\) 的递推式子中得出

因为在第一次循环时，\(l\) 与 \(r\) 明显是 \(l=r\) 的

对我们有用的也只有第 \(0\) 种情况，别的情况因为长度至少都是 \(2\) 而没法参与到第一次循环中

所以只用对 \(dp_{i,i-1,0}\) 赋初始值为 \(1\) 即可

最终时间复杂度 \(O(6\times n^3)\) 不到，（后半部分填不满 \(n^3\) ）。

记得开 long long，并且取模。

#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define N 510
using namespace std;
char s[N];
int n,k,dp[N][N][10];
bool compare(int x,int y){
	return (s[x]=='('||s[x]=='?')&&(s[y]==')'||s[y]=='?');
}
signed main(){
	scanf("%lld%lld%s",&n,&k,s+1);
	for(int i = 1;i<=n;i++) dp[i][i-1][0] = 1;
	for(int len = 1;len<=n;len++){
		for(int l = 1;l<=n-len+1;l++){
			int r = l+len-1;
			if(len<=k) dp[l][r][0] = dp[l][r-1][0]&&(s[r]=='*'||s[r]=='?');
			if(len>=2){
				if(compare(l,r)) dp[l][r][1] = (dp[l+1][r-1][0]+dp[l+1][r-1][2]+dp[l+1][r-1][3]+dp[l+1][r-1][4])%mod;
				for(int i = l;i<=r-1;i++){
					dp[l][r][2] = (dp[l][r][2]+dp[l][i][3]*dp[i+1][r][0])%mod;
					dp[l][r][3] = (dp[l][r][3]+(dp[l][i][2]+dp[l][i][3])*dp[i+1][r][1])%mod;
					dp[l][r][4] = (dp[l][r][4]+dp[l][i][0]*dp[i+1][r][3])%mod;
				}
			}
            dp[l][r][3] = (dp[l][r][3]+dp[l][r][1])%mod;
		}
	}
	printf("%lld",dp[1][n][3]);
	return 0;
}