【GESP真题】GESP七级 / CSP-S 题解:luogu-P17460 [GESP202609 七级] 括号序列

CCF GESP 2026年9月认证（第十五次认证）C++ 七级试题，洛谷 P17460。本题严格遵循 CCF GESP 官方大纲规范，重点考察括号序列平衡度与子序列计数DP。题目逻辑严密，模型典型，是深入理解与掌握信奥核心考点的经典范例。

P17460 [GESP202609 七级] 括号序列

🔗 洛谷原题传送门：P17460

🔹 题目描述

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

例如 sun 是 sequence 的子序列，因为从 sequence 中删除 eq、e 和 ce 可以得到 sun；sequence 有  个不同的子序列，其中有空字符串，也有三个不同的子序列 e，因为 sequence 的第 2, 5, 8 个字符都为 e，分别保留这三个字符得到的子序列是不同的。

对于字符串 ，如果  满足以下条件那么  是合法括号序列：

•  是空字符串，或者
•  可由 (、合法括号序列、) 三者连接得到，或者
•  可由两个合法括号序列连接得到。

例如 ()、()()、(()) 和 (()()) 都是合法括号序列。但是 (()、) ( 不是合法括号序列。

给定一个长度为  的仅包含 ( 与 ) 的字符串 。请你求出  所有  个子序列中有多少个合法括号序列。由于答案可能很大，请你输出答案对  取模的结果。

例如， 为 ))(()( 时共有 3 个子序列是合法括号序列，分别为空字符串与两个不同的子序列 ()。

🔹 输入格式

第一行，一个正整数 ，表示字符串  的长度。

第二行，长度为  的仅包含 ( 与 ) 的字符串 。

🔹 输出格式

输出一行，一个整数，表示  的合法括号子序列的数量对  取模的结果。

🔹 输入输出样例

输入 #1

输出 #1

输入 #2

输出 #2

🔹 说明/提示

数据范围

对于  的测试点，保证 。

对于所有测试点，保证 。

🔹 题目分析与解题思路

1. 合法括号序列充要条件
   ： 任意前缀中未匹配的左括号数量（净差值 ）时刻 ，且最终整个序列结束时净差值恰好为 0。
2. 动态规划状态定义
   ： 设  表示在当前扫描到的前缀中，所有选出的子序列里未匹配左括号数为 （即净差值为 ）的子序列方案数。 初始状态：（空子序列），其余均为 0。
3. 转移逻辑
   ： 依次扫描字符 ： 

   • 若 ：可以选择不选（方案数不变），或者选入当前左括号（净差值从  变为 ）： 
   • 若 ：可以选择不选，或者选入当前右括号（净差值从  变为 ）： 
4. 复杂度
   ：时间复杂度 ，空间利用一维滚动数组仅需 ，毫秒级通过。

🔹 完整参考代码 (C++11)