GESP 题解库 / 7 级题解 / [GESP202609 七级] 括号序列 · 第 24 / 24 题
GESP202609 七级 · P17460 · 困难

括号序列

dp[j] = 选出子序列后当前平衡数为 j 的方案数(过程中平衡数始终 ≥ 0),答案取 dp[0]。

📊
n ≤ 2000
字符串长度
🔢
10⁹ 取模
答案规模
⚡
O(n²) = 4 × 10⁶
时间复杂度
🎯
按"平衡数"计数 DP
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

题目来源:[GESP202609 七级] 括号序列(洛谷 P17460)。

对于字符串 S 与 T,如果从 S 中删除任意多个字符可以得到 T,那么 T 是 S 的子序列。换言之,T 是选取 S 中的若干字符按下标顺序连接而成的。两个子序列不同,当且仅当所选取的下标不同。

例如 sequence 有 2⁸ 个不同的子序列,其中有三个不同的子序列 e,因为它的第 2、5、8 个字符都是 e,分别保留这三个字符得到的子序列被视为不同。

对于字符串 S,如果满足以下条件,则称它是合法括号序列:S 是空字符串;或 S 可由 (、一个合法括号序列、) 三者连接得到;或 S 可由两个合法括号序列连接得到。

输入格式:第一行一个正整数 n,表示 S 的长度;第二行一个长度为 n、仅包含 ( 与 ) 的字符串 S。

输出格式:一行一个整数,表示 S 的合法括号子序列数量对 10⁹ 取模的结果。

例如 S 为 ))(()( 时共有 3 个子序列是合法括号序列:空字符串,以及两个不同的子序列 ()。

1 ≤ n ≤ 2000;40% 的数据 n ≤ 400。

💡
人话翻译,两个要点必须抓住:
① "下标不同即不同子序列"意味着我们数的是选取方案数,而不是"不同字符串的种数"——所以可以直接做方案数 DP,不需要去重;
② 一个括号串合法 ⟺ 任意前缀中 ( 的个数不少于 ),且整体两者数量相等。用"平衡数"(( 记 +1、) 记 −1 的前缀和)说就是:过程中平衡数始终 ≥ 0,最后恰好等于 0。
于是状态只需要记"当前平衡数",转移就是"选 / 不选",复杂度 O(n²)。

🔍 关键词提取

子序列计数括号匹配平衡数(前缀和)方案数 DP前缀非负模 10⁹

已知条件

项目说明
输入第一行 n;第二行长度为 n 的字符串 S
输出合法括号子序列数量对 10⁹ 取模的结果
数据范围1 ≤ n ≤ 2000(40% 数据 n ≤ 400)
字符集只有 ( 与 )
子序列约定按下标选取,下标集合不同即算不同
合法定义空串;( + 合法 + );两个合法串连接

需要解决的问题

02
思维导图
整理解题思路的全貌
🧮 dp[平衡数] = 方案数
🧠 状态设计
dp[j]:当前平衡数为 j 的子序列方案数
j 只取 0 ~ n
初值 dp[0] = 1(空子序列)
答案 = dp[0](含空串)
🔁 转移规则
遇到 ( :不选 → dp[j];选 → dp[j−1](j ≥ 1)
遇到 ) :不选 → dp[j];选 → dp[j+1]
转移天然只在 j ≥ 0 上做
每一步都要 mod 10⁹
✅ 判定依据
前缀 ( 数 ≥ ) 数 ⟺ 平衡数 ≥ 0
总数相等 ⟺ 最终平衡数 = 0
两条都满足 ⟺ 合法括号序列
与"栈匹配"完全等价
⚠️ 易错点
漏掉"过程中非负"这一条
把不同下标组成的同一串去重(会少算)
忘记取模或取模用了 10⁹+7
dp 数组只开到 n(下标会到 n)
03
样例手算推导
样例 1 的逐字符 DP 表 + 样例 2 的组合恒等式核对

🧮 样例 1:n = 6,S = ))(()(,答案 3

先把 6 个字符的下标与内容列清楚,再一步步跑 DP。

下标123456
字符))(()(

手工枚举验证一下答案只有 3 个

合法子序列能怎么选个数
空串一个字符都不选1
()取下标 3 的 ( 与下标 5 的 )1
()取下标 4 的 ( 与下标 5 的 )1
长度为 4 或 6 的串左侧的 ( 只有下标 3、4、6,凑不出"先左后右"的更长结构0

总计 3 ✓

再用 DP 跑一遍(这就是程序里发生的事)

步骤当前字符dp[0]dp[1]dp[2]dp[3]这一步怎么来的
初始—1000空子序列:平衡数 0 有 1 种
1)1000这个 ) 只能"不选":选了平衡数变 −1,非法
2)1000同上,仍然是只能不选
3(1100dp[1] = dp[1] + dp[0] = 0 + 1
4(1210dp[1] = 1 + 1 = 2;dp[2] = 0 + 1 = 1
5)3310dp[0] = dp[0] + dp[1] = 1 + 2 = 3;dp[1] = 2 + 1 = 3
6(3641dp[0] 不变;dp[1] = 3 + 3 = 6;dp[2] = 1 + 3 = 4;dp[3] = 0 + 1 = 1
1
第 5 步(遇到 ))为什么 dp[0] 变成 3

新 dp[0] = 老 dp[0](不选这个 ))+ 老 dp[1](选这个 ))

= 1 + 2 = 3

含义:平衡数仍是 0 的方案有 3 种 —— "空串" + "两个不同的 ()"

✅ 正好对上手工枚举

2
第 6 步(遇到 ()dp[1] 变成 6

新 dp[1] = 老 dp[1](不选)+ 老 dp[0](选)

= 3 + 3 = 6

这个 ( 是下标 6,而它后面已经没有任何字符可以用来配对

所以它只会让"平衡数 1"的方案变多,不会改变 dp[0]

✅ 答案仍是 dp[0] = 3

🔑
看清两条转移的"方向相反":遇到 ( 时新状态从 dp[j−1] 转移来(平衡数 +1);遇到 ) 时新状态从 dp[j+1] 转移来(平衡数 −1)。
而"不选"永远是 dp[j] 原样保留——这正是"每个字符都有选 / 不选两条岔路"的体现,也是 2ⁿ 个子序列的由来。

🧮 样例 2:17 个 ( 接 17 个 ),答案 333606220

样例 2 的 S 是 17 个 ( 后面紧跟 17 个 ),n = 34。这一组可以用组合恒等式独立算出来,正好用来交叉检验我们的 DP。

1
合法子序列长什么样

所有 ( 都在前 17 位,所有 ) 都在后 17 位

任取 i 个 ( 与 i 个 ),按下标拼出来必然是"i 个左 + i 个右"

这种串的前缀左括号数从头到尾都不少于右括号数,且总数相等

所以它一定合法;反之合法的也必然是这样取出来的

合法子序列数 = Σ C(17,i) · C(17,i)(i = 0 ~ 17,i = 0 就是空串)

2
用范德蒙德恒等式化简

Σ C(n,i)² = C(2n, n)

所以 Σ(i = 0 ~ 17) C(17,i)² = C(34,17)

C(34,17) = 2333606220

✅ 精确值 2333606220

3
对 10⁹ 取模

2333606220 mod 1000000000 = 333606220

与样例输出完全一致

这也说明 DP 的取模必须每一步都做,否则 n = 2000 时早就溢出了

✅ 333606220

DP 结果 333606220 ✓

⚠️
这条恒等式是极好的自检工具:如果程序对这一组数据算不出 333606220,多半是犯了两个经典错误之一——
① 丢掉了空串(把 dp[0] 的初值写成 0,或最后手动减了 1);
② 取模出了问题(漏取模导致溢出,或取模常量写成了 10⁹ + 7)。
凡是"答案很大 + 取模"的题,都要尽量找一组能独立算出的数据来交叉核对。
04
解法对比
平衡数 DP vs 枚举 2ⁿ 个子序列 / 组合闭式

⚔️ 解法对比

🟢 平衡数 DP(推荐) 推荐

dp[j] = 当前平衡数为 j 的方案数;每个字符"选 / 不选"两条转移

  • 状态 n + 1 个,转移 O(1),总 O(n²) = 4 × 10⁶
  • n = 2000 时不到 1 毫秒
  • 核心代码约 20 行,逻辑只有两条转移式
  • 天然满足"下标不同即不同子序列"与"前缀非负"两个要求
💡
为什么这一维就够了:括号串是否合法只取决于"每个前缀里左右括号的数量关系",而这个关系完全由当前平衡数刻画。
同时又因为转移只在 j ≥ 0 上进行,"过程中平衡数非负"这条约束被自动满足,不需要额外判断。

🟠 枚举全部 2ⁿ 个子序列

枚举每一个下标选取方案,逐个判断是否合法

  • n = 2000 时是 2²⁰⁰⁰ 种方案
  • 连 n = 30 都跑不动
  • 代码虽短但毫无意义
  • 规模上彻底不可行
⚠️
量级对比:2²⁰⁰⁰ 与 4 × 10⁶,这中间的差距比"宇宙原子总数"和"一百"的差距还夸张。DP 的全部价值,就是把"指数"压成"多项式"。

📈 性能对比

方案复杂度代码量
平衡数 DP(正解)O(n²) ≈ 4 × 10⁶约 20 行
枚举 2ⁿ 个子序列2²⁰⁰⁰❌ 不可行
组合闭式公式仅"全 ( 接全 )"这类特殊结构成立❌ 一般的 S 无闭式
05
算法流程图
逐字符推进,遇到选 / 不选两条转移
开始读入 n 与字符串 Sdp[0] = 1,其余 dp[j] = 0(j = 0 … n)逐个字符 c 处理(共 n 个)c 是 ( 还是 )c = ( ✓ndp[j] = dp[j] + dp[j−1](不选 + 选,j ≥ 1)c = ) ✗ndp[j] = dp[j] + dp[j+1](不选 + 选)把 ndp 拷回 dp,并且每一步都 mod 10⁹输出 dp[0](包含空子序列)处理下一个字符
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🧮 合法括号子序列计数器

第一行输入 n,第二行输入只含 ( 与 ) 的字符串。程序用平衡数 DP 计数,规模较小时还会显示逐字符的 dp 表并做暴力核对。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(平衡数 DP)

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000000;      // 注意是 10⁹,不是 10⁹ + 7
int n;
char S[2005];
long long dp[2005], ndp[2005];

int main() {
    scanf("%d", &n);
    scanf("%s", S + 1);                // 下标从 1 开始,方便书写

    dp[0] = 1;                         // 空子序列:平衡数为 0,方案数 1
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n; j++)   // 情况一:不选第 i 个字符
            ndp[j] = dp[j];

        if (S[i] == '(') {
            for (int j = 1; j <= n; j++)          // 情况二:选它,平衡数 +1
                ndp[j] = (ndp[j] + dp[j - 1]) % MOD;
        } else {
            for (int j = 0; j <= n; j++)          // 情况二:选它,平衡数 −1
                ndp[j] = (ndp[j] + dp[j + 1]) % MOD;
        }

        for (int j = 0; j <= n; j++)   // 滚动:把新状态交给下一轮
            dp[j] = ndp[j];
    }

    printf("%lld\n", dp[0]);           // dp[0] 里已经包含空子序列
    return 0;
}
🔑
"前缀非负"为什么不用额外判断?因为所有转移都只在 j ≥ 0 上进行:选 ( 时从 dp[j−1] 累加,选 ) 时从 dp[j+1] 累加。
如果某个时刻要"选 )"而当前平衡数已经是 0,它只会去读 dp[1] 之类的状态,永远不会产生"平衡数为 −1"的方案——非法前缀在状态层面就被彻底排除了。

📖 关键几行怎么看

代码作用为什么这样写
dp[0] = 1初值空子序列平衡数为 0,算 1 种方案;这也是空串被计入的地方
ndp[j] = dp[j]不选当前字符不进子序列,平衡数不变,方案数原样继承
( 时 ndp[j] += dp[j−1]选 (选一个左括号,平衡数从 j−1 涨到 j,所以从前一档累加
) 时 ndp[j] += dp[j+1]选 )选一个右括号,平衡数从 j+1 降到 j,所以从后一档累加
dp / ndp 轮换滚动数组每轮只依赖上一轮,空间从 O(n²) 压到 O(n)
% 1000000000取模每步都取,防止 n = 2000 时数值溢出;常量是 10⁹
printf("%lld", dp[0])答案平衡数 0 且全程非负 ⟺ 合法括号序列
⚠️
四个坑:① 漏掉"过程非负"(例如把两条转移写成同一个方向,或额外允许 j − 1 < 0 的越界访问),会把 )( 这类串算成合法;② 去重(用 set<string> 收集字符串),题目要求"下标不同即不同",去重必然少算;③ 取模常量写错(本题是 10⁹,不是常见的 10⁹ + 7);④ 数组开小:转移会访问到 dp[n],数组至少要开到 n + 1。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
6
))(()(
3题面样例 1
34
((((((((((((((((()))))))))))))))))
333606220题面样例 2:等于 C(34,17) mod 10⁹
1
(
1只有空串合法(单个左括号配不成对)
1
)
1右括号永远开不了头,同样只剩空串
2
)(
1「)(」不是合法括号序列 —— 这就是"过程中必须非负"的典型
2
()
2空串 + 唯一的「()」
3
(()
3两个不同下标的「()」要分别计数,加空串共 3
4
((((
1全是左括号,凑不出右括号,只剩空串
4
(())
6空串 1 + 长度为 2 的「()」4 个 + 「(())」1 个 = 6
✅
自查清单:① 转移方向对不对(( 从 j−1、) 从 j+1)?② 空串算进去了吗(dp[0] 初值为 1)?③ 每步都 mod 10⁹ 吗?④ 拿 17 个 ( + 17 个 ) 验一下,输出是不是 333606220?

🚨 易错点清单

⚠️
漏掉"过程中平衡数非负":只数"左右数量相等"会把 )(、)(() 这类串也算进去。在 DP 里只要坚持"转移只在 j ≥ 0 上进行",这条约束就自动成立。
⚠️
按"不同字符串"去重:题目说"下标不同即不同子序列",))(()( 里两个不同的 () 要算 2 个;用 set 去重会少算。
⚠️
取模常量写错:本题是 10⁹,不是常见的 10⁹ + 7;同时要每一步都取模,否则数值会溢出。
⚠️
忘掉空串:空子序列也是子序列且合法,dp[0] 的初值 1 已经把它算进去了,最后不要再额外加 1 或减 1。
⚠️
数组开小:转移会读到 dp[n](选 ) 时从 dp[j+1] 取),数组长度至少 n + 1。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n²)
空间复杂度
O(n)
n 最大
2000
运算量
约 4 × 10⁶

时间怎么算的?

空间都用在哪?

只需要两个长度为 n + 1 的数组 dp、ndp。因为每轮只依赖上一轮的结果,用滚动数组把本可以 O(n²) 的状态压到了 O(n)。

✅ 约 400 万次操作,1 秒时限内轻松通过。对比暴力枚举的 2²⁰⁰⁰——一次 DP 就把"指数级"压成了"平方级",这就是动态规划最迷人的地方。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// ① 平衡数 DP 的骨架(会了这一个,改几行就能解一串变体)
dp[0] = 1;
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= n; j++) ndp[j] = dp[j];        // 不选第 i 个字符
    if (S[i] == '(') for (int j = 1; j <= n; j++) ndp[j] = (ndp[j] + dp[j-1]) % MOD;
    else             for (int j = 0; j <= n; j++) ndp[j] = (ndp[j] + dp[j+1]) % MOD;
    for (int j = 0; j <= n; j++) dp[j] = ndp[j];        // 滚动
}
printf("%lld\n", dp[0]);

// ② 判断"一个给定括号串"本身是否合法(计数器写法,与栈等价)
int bal = 0;
bool ok = true;
for (char c : s) {
    bal += (c == '(' ? 1 : -1);
    if (bal < 0) { ok = false; break; }                 // 前缀为负 → 非法
}
if (ok && bal == 0) puts("YES"); else puts("NO");

// ③ 只要"最长合法子序列长度",把存方案数改成存长度
// dp2[j] = 平衡数为 j 时的最大长度(-inf 表示不可达),最后 dp2[0] 即答案

// ④ 再加一维 k 表示"恰好选了 k 个左括号",就变成 O(n²k) 的加强版

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
平衡数(前缀和)把"括号是否匹配"浓缩成一个整数括号匹配、正则括号、栈模拟、括号树
按"变化量"设状态dp[j] 只记当前平衡数,不记整串序列类 DP、状态压缩、LIS 的滚动优化
计数型 DP统计方案数而不是最优值组合计数、路径计数、子序列计数
滚动数组dp / ndp 交替,空间从 O(n²) 到 O(n)所有"只依赖上一层"的 DP
每步取模防止大数溢出、保证结果正确所有"答案对 X 取模"的计数题
🌟
思考题:如果题目改成① "求最长的合法括号子序列有多长",或者 ② "必须恰好选出 k 个左括号",DP 要怎么改?(提示:① 把 dp[j] 里存的值从"方案数"换成"最大长度",不可达记成 −∞,答案取 dp[0];② 再加一维 k,变成 dp[j][k],复杂度 O(n²k)。
同一套"平衡数状态",只改"存什么值"或"多加一维",就能解决一大类括号与序列计数问题——这正是 DP 题目"换个问法就换一版"的典型特征。)