简要题意
给定 \(k\)，定义 “超级括号序列”（简称括号序列，下同) 字符串为：
- 仅由
( ) *三种字符组成。 - 下面令 \(S\) 为不超过 \(k\) 个 \(\ast\) 字符拼接而成的字符串（\(S\) 可以为空字符串）。
- \(\text{(S)}\) 是括号序列。
- 如果 \(A\) 是括号序列，\(\text{(AS)},\text{(SA)}\) 都是括号序列。
- 如果 \(A,B\) 是括号序列，则 \(\text{ASB}\) 是括号序列。
- 特别的，空字符串不是括号序列。
例如，若 \(k = 3\)，则字符串 \(\text{((**()*(*))*)(***)}\) 是括号序列，但字符串 \(\text{*()}\)、\(\text{(*()*)}\)、\(\text{((**))*)}\)、\(\text{(****(*))}\) 均不是。
给你一个长度为 \(n\) 的括号序列 \(s\)，有的字符已经确定，有的字符尚未确定（用 \(\text{?}\) 替代）。求该字符串将所有尚未确定的字符一一确定的方法，使得得到的字符串是一个括号序列？对 \(10^{9}+7\) 取模。
对于 \(100 \%\) 的数据，\(1 \le k \le n \le 500\)。
思路
非常神仙的区间 DP 题。
状态设计
先设状态：
- \(f[l][r][0]\) 为 \([l,r]\) 为 \(S\) 型字符串的个数。如
********。 - \(f[l][r][1]\) 为 \([l,r]\) 为被匹配的括号包裹的字符串个数。如
(*(*(*))*)。 - \(f[l][r][2]\) 为 \([l,r]\) 为以括号序列开头，\(\ast\) 结尾的字符串个数。如
(*(*)*)***(*)*。 - \(f[l][r][3]\) 为 \([l,r]\) 为以括号序列开头与结尾的字符串个数，包含 \(f[l][r][2]\)。
- \(f[l][r][4]\) 为 \([l,r]\) 为以括号序列结尾，\(\ast\) 开头的字符串个数，如
****(*(***))。 - \(f[l][r][5]\) 为 \([l,r]\) 为以 \(\ast\) 开头或结尾的个数，包含 \(f[l][r][0]\)。
状态转移
\[f[l][r][0]=\left\{ \begin{aligned} & f[l][r-1][0] & \operatorname{ast}(r)\\ & 0 & \text{otherwise} \end{aligned} \right. \]解释：\(\operatorname{ast}(r)\) 指 \(s_r\) 可能为 \(\ast\)。如果不是 \(\ast\) 自然没有了。
\[f[l][r][1]=\left\{ \begin{aligned} & (f[l+1][r-1][0]+f[l+1][r-1][2]+f[l+1][r-1][3]+f[l+1][r-1][4])& \operatorname{match(l,r)} \\ & 0 & \text{otherwise} \end{aligned} \right. \]解释：\(\operatorname{match}(l,r)\) 为 \(s_l,s_r\) 可能括号匹配。加括号的时候，除了两边都是 \(\ast\) 且中间有括号序列外，其他都可以。
\[\begin{aligned} &f[l][r][2]=\sum_{i=l}^{r-1}f[l][i][3]\cdot f[i+1][r][0] \\ &f[l][r][3]=(\sum_{i=l}^{r}(f[i+1][r]\cdot (f[l][i][2]+f[l][i][3]))+f[l][r][1]) \\ &f[l][r][4]=\sum_{i=l}^{r}f[i+1][r][1]\cdot (f[l][i][4]+f[l][i][5]) \\ &f[l][r][5]=(\sum_{i=l}^{r}f[l][i][4]\cdot f[i+1][r][0])+f[l][r][0] \end{aligned} \]- \(f[l][r][2]\) 中是括号序列开头（3）接 \(\ast\)（0）
- \(f[l][r][3]\) 可以是 2,3 开头，必须是 0 结尾
- \(f[l][r][4]\) 可以是4,5 开头，必须是 1 结尾
- \(f[l][r][5]\) 可以是4 开头，0 结尾。
最后答案就是 \(f[1][n][3]\)。
时间复杂度 \(O(n^3)\)。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int f[505][505][10];
char s[505];
int n,k;
const int MOD = 1e9+7;
inline bool is_star(int pos){
return (s[pos]=='*'||s[pos]=='?');
}
inline bool is_left_bracket(int pos){
return (s[pos]=='('||s[pos]=='?');
}
inline bool is_right_bracket(int pos){
return (s[pos]==')'||s[pos]=='?');
}
inline bool is_brackets_matched(int left,int right){
return is_left_bracket(left)&&is_right_bracket(right);
}
int m(int x){return (x%MOD+MOD)%MOD;}
void M(int &x){x=m(x);}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>k;
cin>>(s+1);
for(int i=1;i<=n;i++){
f[i][i-1][0]=1;
}
for(int length=1;length<=n;length++){
for(int l=1,r=length;l<=n&&r<=n;l++,r++){
// 处理情况 0
if(length<=k && f[l][r-1][0] && is_star(r))f[l][r][0]=1;
else f[l][r][0]=0;
// 处理情况 1
if(length>1 && is_brackets_matched(l,r)){
f[l][r][1]=m(f[l+1][r-1][0]+f[l+1][r-1][2]+f[l+1][r-1][3]+f[l+1][r-1][4]);
}
// 处理情况 2
if(length>1){
for(int i=l;i<r;i++){
f[l][r][2] += m(f[l][i][3]*f[i+1][r][0]);
M(f[l][r][2]);
}
}
// 处理情况 3
if(length>1){
for(int i=l;i<r;i++){
f[l][r][3] += m(m(f[l][i][2]+f[l][i][3])*f[i+1][r][1]);
M(f[l][r][3]);
}
}
f[l][r][3] += f[l][r][1];M(f[l][r][3]);
// 处理情况 4
if(length>1){
for(int i=l;i<r;i++){
f[l][r][4] += m(m(f[l][i][4]+f[l][i][5])*f[i+1][r][1]);
M(f[l][r][4]);
}
}
// 处理情况 5
if(length>1){
for(int i=l;i<r;i++){
f[l][r][5] += m(f[l][i][4]*f[i+1][r][0]);
M(f[l][r][5]);
}
}
f[l][r][5]+=f[l][r][0];M(f[l][r][5]);
}
}
cout<<m(f[1][n][3]);
return 0;
}