问题分析

本题要求统计所有可能的合法超级括号序列数量，其中序列由 (、)、* 组成，且需要满足给定的语法规则。这是一个典型的区间DP计数问题。

核心思路

语法规则解析 根据题目定义，合法序列的生成规则为：

基础规则：() 和 (S)（其中 $S$ 是长度 $\leq k$ 的星号串）

连接规则：$AB$ 和 $ASB$（$A,B$ 为合法序列）

嵌套规则：(A)、(SA)、(AS)

状态设计

定义两个DP数组：

• f[l][r]：表示区间 $[l,r]$ 形成一个不可分割的合法序列的方案数

• g[l][r]：表示区间 $[l,r]$ 形成一个任意合法序列的方案数

算法详解

预处理

// 前缀和：统计区间内可填星号的位置数
for (int i = 1; i <= n; i++)
    sum[i] = sum[i - 1] + (a[i] == '*' || a[i] == '?');

// 检查两端是否能形成匹配括号
inline bool cp(int l, int r) {
    return (a[l] == '(' || a[l] == '?') && (a[r] == ')' || a[r] == '?');
}

// 检查区间是否全为星号
inline bool full(int l, int r) {
    return gs(l, r) == r - l + 1;
}

动态规划转移

1.基础情况

if (len == 2) {
    if (cp(l, r))
        f[l][r] = g[l][r] = 1;  // 只有 "()" 这种情况
}

2.外层括号匹配的情况

当 cp(l, r) 为真时（即首尾可以形成匹配括号）：

(a) 直接嵌套

g[l][r] = g[l + 1][r - 1];
f[l][r] = g[l + 1][r - 1];

(b) 星号包围的情况 (S)

if (full(l + 1, r - 1) && (r - 1) - (l + 1) + 1 <= k)
    g[l][r]++, f[l][r]++;

(c) 左侧星号 (SA)

for (int i = l + 1; i < r; i++) {
    if (i - l > k) break;
    if (full(l + 1, i)) {
        g[l][r] += g[i + 1][r - 1];
        f[l][r] += g[i + 1][r - 1];
    }
}

(d) 右侧星号 (AS)

for (int i = r - 1; i > l; i--) {
    if (r - i > k) break;
    if (full(i, r - 1)) {
        g[l][r] += g[l + 1][i - 1];
        f[l][r] += g[l + 1][i - 1];
    }
}

(e) 连接情况 ASB

int las = l;
pre[l - 1] = 0;
for (int i = l; i <= r; i++) {
    pre[i] = pre[i - 1] + g[l][i];  // 前缀和优化
    
    if (a[i] == '(' || a[i] == ')')
        las = i - 1;
    
    while (i - las > k + 1)
        las++;
    
    // g[l][i] * f[i+1][r] 表示 A*B 的连接方式
    g[l][r] += (pre[i] - pre[las]) % M * f[i + 1][r] % M;
}

复杂度分析

时间复杂度

• 外层循环：$O(n^2)$（所有区间）

• 内层循环：$O(n)$（分割点枚举）

• 总复杂度：$O(n^3)$，对于 $n \leq 500$ 可接受

空间复杂度

$O(n^2)$ 存储DP数组

关键优化

前缀和优化：快速判断区间是否全为星号

提前终止：星号长度超过 $k$ 时立即跳出循环

双DP数组：f 和 g 分别处理不同语义，避免重复计数

样例验证

样例1：n=7, k=3, "(????"

输出为 5，符合预期

可能的序列包括：(*****)、(()*) 等

总结

本题通过精心设计的DP状态和转移方程，完整覆盖了超级括号序列的所有生成规则。算法充分利用了区间DP的特性，通过前缀和等优化手段保证了在合理时间内求解。关键在于理解不同语法规则对应的区间分割方式，并正确统计各种情况下的方案数。

AC代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 505, M = 1000000007;
int n, k, f[N][N], g[N][N], sum[N], pre[N];
string a;
inline int gs(int l, int r) {
    return sum[r] - sum[l - 1];
}
inline bool cp(int l, int r) {
    return (a[l] == '(' || a[l] == '?') && (a[r] == ')' || a[r] == '?');
}
inline bool full(int l, int r) {
    return gs(l, r) == r - l + 1;
}
signed main() {
    //freopen("bracket.in", "r", stdin);
    //freopen("bracket.out", "w", stdout);
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> k >> a;
    a = ' ' + a;

    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + (a[i] == '*' || a[i] == '?');

    for (int len = 2; len <= n; len++)
        for (int l = 1, r = l + len - 1; r <= n; l++, r++) {
            if (len == 2) {
                if (cp(l, r))
                    f[l][r] = g[l][r] = 1;

                continue;
            }

            if (cp(l, r)) {
                g[l][r] = g[l + 1][r - 1];
                f[l][r] = g[l + 1][r - 1];

                if (full(l + 1, r - 1) && (r - 1) - (l + 1) + 1 <= k)
                    g[l][r]++, f[l][r]++;

                for (int i = l + 1; i < r; i++) {
                    if (i - l > k)
                        break;

                    if (full(l + 1, i)) {
                        g[l][r] += g[i + 1][r - 1];
                        f[l][r] += g[i + 1][r - 1];
                    }
                }

                for (int i = r - 1; i > l; i--) {
                    if (r - i > k)
                        break;

                    if (full(i, r - 1)) {
                        g[l][r] += g[l + 1][i - 1];
                        f[l][r] += g[l + 1][i - 1];
                    }
                }

                int las = l;
                pre[l - 1] = 0;

                for (int i = l; i <= r; i++) {
                    pre[i] = pre[i - 1] + g[l][i];

                    if (a[i] == '(' || a[i] == ')')
                        las = i - 1;

                    while (i - las > k + 1)
                        las++;

                    g[l][r] += (pre[i] - pre[las]) % M * f[i + 1][r] % M;
                }

                f[l][r] %= M, g[l][r] %= M;
                //  cout << l << ' ' << r << ' ' << f[l][r] << ' ' << g[l][r] << '\n';
            }
        }

    cout << g[1][n];
    return 0;
}