xmlns="http://www.w3.org/2000/svg"

style="display:

none;">

2021信奥赛C++提高组csp-s复赛真题及题解：括号序列

在赛场上遇到了这样一个题：一个长度为n

nn且符合规范的括号序列，其有些位置已经确定了，有些位置尚未确定，求这样的括号序列一共有多少个。

身经百战的小

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

定义“超级括号序列”是由字符(、)、*组成的字符串，并且对于某个给定的常数k

style="margin-right:

0.0315em;">k，给出了“符合规范的超级括号序列”的定义如下：

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

4. 所有符合规范的超级括号序列均可通过上述

   条规则得到。

例如，若k

=

0.0315em;">k=3，则字符串((**()*(*))*)(***)是符合规范的超级括号序列，但字符串*()、(*()*)、((**))*)、(****(*))均不是。

特别地，空字符串也不被视为符合规范的超级括号序列。

现在给出一个长度为n

nn的超级括号序列，其中有一些位置的字符已经确定，另外一些位置的字符尚未确定（用?表示）。

小

希望能计算出：有多少种将所有尚未确定的字符一一确定的方法，使得得到的字符串是一个符合规范的超级括号序列？

可怜的小

并不会做这道题，于是只好请求你来帮忙。

输入格式

第一行，两个正整数n

kn,

style="margin-right:

0.0315em;">k。

第二行，一个长度为n

nn且仅由(、)、*、?构成的字符串S

style="margin-right:

0.0576em;">S。

输出格式

输出一个非负整数表示答案对10

+

710

style="height:

0.05em;">9+7取模的结果。

输入输出样例

1

输入

1

5

输入输出样例

2

输入

2

19

说明/提示

【样例解释

#1】

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

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

【数据范围】

对于100

100

\%100%的数据，1

500

5001≤

style="margin-right:

0.0315em;">k≤n≤500。

思路分析

状态定义

定义dp[l][r][t]表示区间[l,

r]在状态t下的方案数，其中t有6种状态：

• dp[l][r][0]:

  区间[l,

  k

• dp[l][r][1]:

  区间[l,

  r]是(A)形式的合法序列（A可以是多种状态）

• dp[l][r][2]:

  区间[l,

  r]是A*B形式，且以*结尾

• dp[l][r][3]:

  区间[l,

  r]是完整的合法序列（最终答案状态）

• dp[l][r][4]:

  区间[l,

  r]是(A*B)形式，且以)结尾

• dp[l][r][5]:

  区间[l,

  r]是A*形式，且以*结尾

转移方程

1. 状态0：全是*且长度

   =

   (s[r]=='*'||s[r]=='?')

2. 状态1：(A)形式

   • 要求s[l]=='('且s[r]==')'
   • dp[l][r][1]

     =

     dp[l+1][r-1][4]

3. 状态2：A*B形式，以*结尾

   • 枚举分割点i，要求[i+1,

     r]是状态0

   • dp[l][r][2]

     +=

     dp[i+1][r][0]

4. 状态3：完整合法序列

   • 从状态1直接转移：dp[l][r][3]

     +=

     dp[l][r][1]

   • 从拼接转移：dp[l][r][3]

     +=

     dp[i+1][r][1]

5. 状态4：(A*B)形式，以)结尾

   • dp[l][r][4]

     +=

     dp[i+1][r][1]

6. 状态5：A*形式，以*结尾

   • 从状态0直接转移：dp[l][r][5]

     +=

     dp[l][r][0]

   • 从拼接转移：dp[l][r][5]

     +=

     dp[i+1][r][0]

初始化

• dp[i][i-1][0]

  =

  1：处理空串

代码实现

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=505;constintmod=1e9+7;intn,k;chars[N];ll
dp[N][N][6];//
判断字符是否匹配括号boolcheck(chara,charb){return(a=='('||a=='?')&&(b==')'||b=='?');}intmain(){scanf("%d%d",&n,&k);scanf("%s",s+1);//
初始化：空串是合法的全*串for(inti=1;i<=n;i++){dp[i][i-1][0]=1;}//
区间DPfor(intlen=1;len<=n;len++){for(intl=1;l+len-1<=n;l++){intr=l+len-1;//
状态0:
全*串，长度≤kif(len<=k){dp[l][r][0]=dp[l][r-1][0]&&(s[r]=='*'||s[r]=='?');}//
长度≥2才可能形成括号序列if(len>=2){//
状态1:
(A)形式if(check(s[l],s[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(inti=l;i<r;i++){//
状态2:
A*B形式，以*结尾//
A是状态3，B是状态0dp[l][r][2]=(dp[l][r][2]+dp[l][i][3]*dp[i+1][r][0])%mod;//
状态3:
B是状态1dp[l][r][3]=(dp[l][r][3]+(dp[l][i][2]+dp[l][i][3])*dp[i+1][r][1])%mod;//
状态4:
(A*B)形式，以)结尾//
A是状态4或5，B是状态1dp[l][r][4]=(dp[l][r][4]+(dp[l][i][4]+dp[l][i][5])*dp[i+1][r][1])%mod;//
状态5:
A*形式，以*结尾//
A是状态4，B是状态0dp[l][r][5]=(dp[l][r][5]+dp[l][i][4]*dp[i+1][r][0])%mod;}}//
状态5也可以直接是全*串dp[l][r][5]=(dp[l][r][5]+dp[l][r][0])%mod;//
状态3也可以直接是状态1dp[l][r][3]=(dp[l][r][3]+dp[l][r][1])%mod;}}//
答案：整个字符串是完整合法序列printf("%lld\n",dp[1][n][3]);return0;}

功能分析

1.

状态设计

这种6状态设计非常精妙：

• 状态0：处理全星号串，限制长度≤k
• 状态1：处理最基础的括号包裹形式(A)
• 状态2：处理A*形式的拼接（右边是星号串）
• 状态3：处理完整的合法序列（最终答案）
• 状态4：处理(A*B)形式的中间状态
• 状态5：处理A*形式的另一状态

2.

转移逻辑

• 避免重复计算：通过严格的状态划分，确保每种合法序列只被计算一次
• 处理拼接规则：通过枚举分割点i，处理各种拼接情况
• 处理括号嵌套：通过状态1处理括号嵌套的情况

3.

时间复杂度

• 三重循环：O(n³)，其中外层循环len，内层循环l和分割点i
• 对于n=500，大约需要500³

  =

  1.25亿次运算，可接受

4.

空间复杂度

• dp[N][N][6]：500×500×6

  =

  long，约12MB内存

5.

正确性保证

• 完全按照题目给出的4条规则进行状态转移
• 状态3是最终答案，包含所有合法序列
• 通过取模运算防止溢出

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"##########
一站式掌握信奥赛知识!
##########";cout<<"#############
冲刺信奥赛拿奖!
#############";cout<<"######
######";return0;}

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<"
";cout<<"
csp信奥赛一等奖属于你!
";return0;}