思路与算法

区间DP区分单个最外层括号块P、完整序列F、星串+完整序列SF、完整序列+星串FS。P内部仅可为空、短星串、F、SF或FS。F按第一个完整括号块及其后可选短星串拆分，避免重复计数。

正确性说明

任意合法完整序列的首个左括号有唯一匹配右括号，确定唯一首块P；接下来连续星串长度也唯一，剩余必须仍为F。单块内部按规则恰有五类，互不重叠：空、纯星、首尾括号的F、仅前缀星、仅后缀星。按长度递增计算所有更短状态，计数覆盖全部合法替换且不重复。

复杂度

O(n³)时间、O(n²)空间，n<=500；含四状态矩阵及星串可行前缀表初始化。

易错点

不能在同一括号内同时加前后星串；空串不是合法完整序列。?可选择三种字符，星串非空且长度不超过k；每次累加及时取模。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct DS {
    vector<int> p, s;
    DS(int n) : p(n), s(n, 1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int u) {
        while (p[u] != u) {
            p[u] = p[p[u]];
            u = p[u];
        }
        return u;
    }
    bool join(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return false;
        if (s[a] > s[b])
            swap(a, b);
        p[a] = b;
        s[b] += s[a];
        return true;
    }
};

int main() {
    int n, k;
    string s;
    cin >> n >> k >> s;
    const long long M = 1000000007;
    vector<vector<long long>> p(n, vector<long long>(n)), f = p, sf = p, fs = p;
    vector<int> bad(n + 1);
    for (int i = 0; i < n; i++)
        bad[i + 1] = bad[i] + (s[i] != '*' && s[i] != '?');
    auto stars = [&](int l, int r) {
        return l <= r && r - l + 1 <= k && bad[r + 1] == bad[l];
    };
    for (int len = 1; len <= n; len++)
        for (int l = 0, r = len - 1; r < n; l++, r++) {
            if (len >= 2 && (s[l] == '(' || s[l] == '?') && (s[r] == ')' || s[r] == '?')) {
                if (len == 2)
                    p[l][r] = 1;
                else
                    p[l][r] = (stars(l + 1, r - 1) + f[l + 1][r - 1] + sf[l + 1][r - 1] +
                               fs[l + 1][r - 1]) %
                              M;
            }
            long long v = p[l][r];
            for (int j = l + 1; j < r; j++)
                v = (v + p[l][j] * ((f[j + 1][r] + sf[j + 1][r]) % M)) % M;
            f[l][r] = v;
            for (int j = l; j < r && j - l + 1 <= k; j++)
                if (stars(l, j))
                    sf[l][r] = (sf[l][r] + f[j + 1][r]) % M;
            for (int j = r; j > l && r - j + 1 <= k; j--)
                if (stars(j, r))
                    fs[l][r] = (fs[l][r] + f[l][j - 1]) % M;
        }
    cout << f[0][n - 1] << "\n";
}