[CSP-S 2021] 括号序列

GitHub跳转原题关系图返回列表

用区间 DP 分别统计单个外层括号块和由多个块拼接成的合法超级括号序列。

OJ: luogu

题目 ID: P7914

难度:提高+/省选-

标签:动态规划区间 DP字符串

创建: 2026-07-06 08:46

更新: 2026-10-07 10:45

形式化题目

给定长度为 $n$ 的字符串 $S$ ，每个位置可能是 '('、')'、'*' 或 '?'。要求将所有 '?' 替换为 '('、')' 或 '*'，使得最终字符串是符合定义的"超级括号序列"。

定义（给定常数 $k$ ）：

() 和 (S) 是合法序列，其中 $S$ 是长度 $1 \sim k$ 的纯 '*' 串
若 $A$ 、 $B$ 均合法，则 $AB$ 、 $ASB$ 均合法
若 $A$ 合法，则 $(A)$ 、 $(SA)$ 、 $(AS)$ 均合法

求合法替换方案数，对 $10^9 + 7$ 取模。

暴力解法

思路

小数据下枚举所有 '?' 的替换（每个 '?' 有 3 种选择），再递归判断最终字符串是否合法。

判断合法性时记忆化： $valid[l][r]$ 表示区间 $[l,r]$ 是否为合法序列， $atom[l][r]$ 表示是否为单个外层括号块。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-06 08:46
 * update_at: 2026-10-01 20:57
 */
// brute.cpp：小数据暴力解，枚举所有 ? 的替换，再用递归判断定义是否合法。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll MOD = 1000000007LL;

int n, K;
string pattern_s, cur;
vector<int> question_pos; // 所有 '?' 的位置

// memo_valid[l][r]：区间 [l,r] 是否为合法超级括号序列，-1 未计算，0/1 表示结果
// memo_atom[l][r]：区间 [l,r] 是否为单个外层括号块，-1 未计算，0/1 表示结果
int memo_valid[20][20];
int memo_atom[20][20];
ll answer;

// 区间 [l,r] 是否能全部填成星号（长度不超过 K 且每个位置都是 '*'）
bool is_star_string(int l, int r) {
    if (l > r) return false;
    if (r - l + 1 > K) return false;
    for (int i = l; i <= r; i++) {
        if (cur[i] != '*') return false;
    }
    return true;
}

bool is_valid(int l, int r);

// 区间 [l,r] 是否为单个外层括号块
bool is_atom(int l, int r) {
    if (l >= r) return false;
    if (memo_atom[l][r] != -1) return memo_atom[l][r];
    bool ok = false;
    if (cur[l] == '(' && cur[r] == ')') {
        if (l + 1 == r) ok = true;                                 // ()
        if (is_star_string(l + 1, r - 1)) ok = true;              // (S)
        if (l + 1 <= r - 1 && is_valid(l + 1, r - 1)) ok = true;  // (A)
        for (int p = l + 1; p <= r - 2; p++) {
            if (is_star_string(l + 1, p) && is_valid(p + 1, r - 1)) ok = true; // (SA)
            if (is_valid(l + 1, p) && is_star_string(p + 1, r - 1)) ok = true; // (AS)
        }
    }
    memo_atom[l][r] = ok;
    return ok;
}

// 区间 [l,r] 是否为合法超级括号序列
bool is_valid(int l, int r) {
    if (l > r) return false;
    if (memo_valid[l][r] != -1) return memo_valid[l][r];
    bool ok = is_atom(l, r);
    for (int start = l + 1; start <= r && !ok; start++) {
        if (!is_atom(start, r)) continue;
        if (is_valid(l, start - 1)) ok = true;                    // AB
        for (int star_len = 1; star_len <= K && start - star_len - 1 >= l; star_len++) {
            int star_l = start - star_len;
            int left_r = star_l - 1;
            if (is_star_string(star_l, start - 1) && is_valid(l, left_r)) {
                ok = true;                                         // ASB
            }
        }
    }
    memo_valid[l][r] = ok;
    return ok;
}

// 枚举第 idx 个 '?' 的替换（'(' / ')' / '*'）
void dfs_replace(int idx) {
    if (idx == (int)question_pos.size()) {
        memset(memo_valid, -1, sizeof(memo_valid));
        memset(memo_atom, -1, sizeof(memo_atom));
        if (is_valid(1, n)) {
            answer++;
            if (answer >= MOD) answer -= MOD;
        }
        return;
    }

    int pos = question_pos[idx];
    cur[pos] = '(';
    dfs_replace(idx + 1);
    cur[pos] = ')';
    dfs_replace(idx + 1);
    cur[pos] = '*';
    dfs_replace(idx + 1);
    cur[pos] = '?';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> K >> pattern_s;
    cur = " " + pattern_s;
    for (int i = 1; i <= n; i++) {
        if (cur[i] == '?') {
            question_pos.push_back(i);
        }
    }

    dfs_replace(0);
    cout << (answer % MOD) << '\n';
    return 0;
}

复杂度

时间： $O(3^{q} \cdot n^3)$ ， $q$ 为 '?' 个数，判断合法性用记忆化递归
空间： $O(n^2)$ ，记忆化数组

瓶颈

'?' 个数稍大就会指数爆炸，只能处理 $n \leqslant 15$ 左右的小数据。

正解

思路

为了避免拼接规则产生重复计数，区分两类状态：

$atom[l][r]$ ：区间 $[l,r]$ 是一个单个外层括号块
$f[l][r]$ ：区间 $[l,r]$ 是一个完整合法超级括号序列，可能由多个 $atom$ 拼接而成

一个 $atom$ 必须形如外层一对括号：

text

1
2
3
4
5()
(S)
(A)
(SA)
(AS)

其中 $S$ 是长度 $1 \sim k$ 的星号串， $A$ 是一个合法序列（即 $f$ 状态）。

而一个完整序列 $f[l][r]$ 可以是：

单个 $atom[l][r]$
前面一段完整序列，加上后面的一个 $atom$
前面一段完整序列，中间隔一个长度不超过 $k$ 的星号串，再加后面的一个 $atom$

这种"按最后一个 atom 来拆"的方式是唯一的，因此不会把 $A B C$ 这样的串用不同括号方式重复统计。

代码中 $sep\_sum[l][start]$ 表示：从 $l$ 开始的一段合法序列，后面接空串或一段合法星号串后，使下一个 $atom$ 从 $start$ 开始的方案数。这样转移 $f[l][r]$ 时只需要枚举最后一个 $atom$ 的起点 $start$ 。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-06 08:46
 * update_at: 2026-10-01 20:57
 */
// main.cpp：区间 DP，atom 表示单个外层括号块，f 表示若干 atom 拼成的合法序列。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 505;
const ll MOD = 1000000007LL;

int n, K;
string s;

// bad_star_prefix[i]：前缀 [1,i] 中不能当 '*' 的位置数（即不是 '*' 也不是 '?' 的位置）
int bad_star_prefix[MAXN];

// atom_dp[l][r]：区间 [l,r] 构成单个外层括号块的方案数
int atom_dp[MAXN][MAXN];

// f[l][r]：区间 [l,r] 构成合法超级括号序列的方案数（可由多个 atom 拼接）
int f[MAXN][MAXN];

// sep_sum[l][r]：从 l 开始的一段合法序列，后面接空串或星串，使下一个 atom 从 r 开始的方案数
int sep_sum[MAXN][MAXN];

// 位置 pos 能否放左括号 '('
bool can_left(int pos) {
    return s[pos] == '(' || s[pos] == '?';
}

// 位置 pos 能否放右括号 ')'
bool can_right(int pos) {
    return s[pos] == ')' || s[pos] == '?';
}

// 位置 pos 能否放星号 '*'
bool can_star_char(int pos) {
    return s[pos] == '*' || s[pos] == '?';
}

// 区间 [l,r] 是否能全部填成星号（长度不超过 K 且每个位置都能放 '*'）
bool is_star_string(int l, int r) {
    if (l > r) {
        return false;
    }
    if (r - l + 1 > K) {
        return false;
    }
    return bad_star_prefix[r] - bad_star_prefix[l - 1] == 0;
}

// 模意义下加法：x = (x + y) % MOD
void add_mod(int &x, ll y) {
    x = (x + y) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> K;
    cin >> s;
    s = " " + s;

    for (int i = 1; i <= n; i++) {
        bad_star_prefix[i] = bad_star_prefix[i - 1] + (can_star_char(i) ? 0 : 1);
    }

    for (int len = 1; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;

            // 计算 sep_sum[l][r]：f[l][..] 后接空串或星串，使下一个 atom 从 r 开始
            if (l < r) {
                sep_sum[l][r] = f[l][r - 1]; // 两个合法块直接相接
                int max_len = min(K, r - l - 1);
                for (int star_len = 1; star_len <= max_len; star_len++) {
                    int star_l = r - star_len;
                    int left_end = star_l - 1;
                    if (left_end >= l && is_star_string(star_l, r - 1)) {
                        add_mod(sep_sum[l][r], f[l][left_end]);
                    }
                }
            }

            // 计算 atom_dp[l][r]：区间 [l,r] 是单个外层括号块
            if (len >= 2 && can_left(l) && can_right(r)) {
                if (l + 1 == r) {
                    add_mod(atom_dp[l][r], 1); // ()
                }
                if (is_star_string(l + 1, r - 1)) {
                    add_mod(atom_dp[l][r], 1); // (S)
                }
                if (l + 1 <= r - 1) {
                    add_mod(atom_dp[l][r], f[l + 1][r - 1]); // (A)
                }

                // (SA)
                for (int p = l + 1; p <= r - 2 && p - (l + 1) + 1 <= K; p++) {
                    if (is_star_string(l + 1, p)) {
                        add_mod(atom_dp[l][r], f[p + 1][r - 1]);
                    }
                }

                // (AS)
                for (int p = l + 1; p <= r - 2; p++) {
                    if (is_star_string(p + 1, r - 1)) {
                        add_mod(atom_dp[l][r], f[l + 1][p]);
                    }
                }
            }

            // 计算 f[l][r]：单个 atom 或多个 atom 拼接
            f[l][r] = atom_dp[l][r];
            for (int start = l + 1; start <= r; start++) {
                add_mod(f[l][r], (ll)sep_sum[l][start] * atom_dp[start][r]);
            }
        }
    }

    cout << f[1][n] << '\n';
    return 0;
}

复杂度

时间： $O(n^3)$ ，区间数 $O(n^2)$ ，计算 $atom$ 和分隔星号串需要枚举区间内部位置
空间： $O(n^2)$

总结

本题最重要的是防止重复计数。把合法串拆成"若干个单独括号块 $atom$ 的序列"，并固定按最后一个 $atom$ 来转移，就能把语法规则变成稳定的区间 DP。

P7914 [CSP-S 2021] 括号序列

题目描述

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

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

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

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

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

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

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

输入格式

第一行，两个正整数 $n, k$ 。

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

输出格式

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

输入输出样例 #1

输入 #1

text

1
27 3
(*??*??

输出 #1

text

输入输出样例 #2

输入 #2

text

1
210 2
???(*??(?)

输出 #2

text

输入输出样例 #3

输入 #3

text

1见附件中的 bracket/bracket3.in

输出 #3

text

1见附件中的 bracket/bracket3.ans

输入输出样例 #4

输入 #4

text

1见附件中的 bracket/bracket4.in

输出 #4

text

1见附件中的 bracket/bracket4.ans

说明/提示

【样例解释 #1】

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

plain

1
2
3
4
5(**)*()
(**(*))
(*(**))
(*)**()
(*)(**)

【数据范围】

测试点编号	$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$ 。

[CSP-S 2021] 括号序列

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

思路

代码

复杂度

总结