ARTICLE · 1126190

真题解析:P7914 [CSP-S 2021] 括号序列(区间DP·唯一分解去重·组合计数·前缀和优化)

发布时间：2026-10-05 10:24:14 最近访问：2026-10-05 10:24:15

题目来源：洛谷 P7914 [CSP-S 2021] 括号序列

题目大意

定义“符合规范的超级括号序列”为由字符 (、)、* 组成的字符串，满足以下递归规则（其中 S 表示任意一段长度在 1 到 k 之间、仅由 * 组成的非空串）：

• 基础：()、(S) 都是规范的；
• 并置：若 A、B 规范，则 AB、ASB 规范；
• 包裹：若 A 规范，则 (A)、(SA)、(AS) 规范；
• 空串不是规范的超级括号序列。

给定一个正整数 n、一个正整数 k，以及一个长度为 n、字符集为 (、)、*、? 的字符串。其中每个 ? 都可以独立地填成 (、) 或 *。求有多少种填法，使得填好的整个串成为一个符合规范的超级括号序列。答案对 10^9+7 取模。

直观理解：* 只能出现在括号内部，或者夹在两块括号序列之间，所以任何合法串首字符必是 (、尾字符必是 )。

输入输出样例

样例 1 输入：

7 3(*??*??

样例 1 输出：

样例 1 共有 5 种合法填法：(**)*()、(**(*))、(*(**))、(*)**()、(*)(**)。

样例 2 输入：

10 2???(*??(?)

样例 2 输出：

（样例 3、样例 4 的数据在洛谷题目附件 bracket.zip 中，需登录后下载，这里不再列出。）

考点梳理

考点	在本题里的作用
区间 DP	状态定义在子区间 `[i,j]` 上，按区间长度递增计算，短区间答案先算好供长区间转移复用
括号匹配的唯一分解	以“首字符 `(` 匹配其真实对应的 `)`”为骨架，保证每个合法串只被统计一次，避免重复计数
字符串组合计数	用 `canL`/`canR`/`canStar` 三个 0/1 指示表示 `?` 可充当的角色，方案数按角色相乘累加
取模运算	答案对 `10^9+7` 取模，乘法中间量用 `long long` 承接防溢出，减法后修正负数
前缀和优化	用 `bad` 前缀和把“一段能否全是星”判定压到 `O(1)`，整体复杂度降到 `O(n^3)`

解题思路

一、把递归文法翻译成 DP 状态

观察规则可知，* 只能在括号内出现，或者在两个合法序列之间出现。因此一个合法串必然由若干“块”首尾相接组成，块与块之间可以夹 0 个或多个 *。把“块”定义为最外层一对括号互相匹配的序列 (X)，于是：

• 相邻两块紧挨着，对应规则 AB；
• 相邻两块之间夹 1..k 个 *，对应规则 ASB。

这个分解是唯一的：块的边界就是第一层括号恢复平衡的位置，给定字符串后，块和夹层星串就唯一确定。把“块 / 序列”拆成两层，是后面去重的关键。

据此在子区间 [i,j] 上定义三套状态（下文变量名与参考代码完全一致）：

• V[i][j]：区间 [i,j] 本身是一个完整规范超级括号序列的方案数；
• E[i][j]：区间 [i,j] 作为“一对括号之间的内容物”，即 E = S | V | SV | VS（注意没有 SVS，规则里没有 (SVS)）；
• CONT[i][j]：区间 [i,j] 作为“某对括号闭合之后接续的内容”，即 CONT = V 或 S + V，专门处理块与块之间的星串（ASB）。

二、用“首括号匹配”做唯一分解（去重核心）

最朴素的“包裹 + 拼接”写法会把 (()()) 这类串重复计数——它在 A|BC 和 AB|C 两处各被统计一次。解决办法是人为规定一种唯一的分解：

对任一合法串，其首字符 ( 真实匹配的 ) 位置 p 是唯一确定的。以 p 为骨架，内部 [i+1,p-1] 作为内容物 E，其后 [p+1,j] 作为接续 CONT。这样每个合法串恰好落在唯一的 p 上，只被统计一次。

三、三套区间 DP 的定义与含义

V[i][j] 的转移就是“首括号 i 匹配位置 p 的 )，内部取 E[i+1][p-1]，其后取 CONT[p+1][j]”，再乘上 canL[i]·canR[p]（首尾能否分别是 ( 和 )）：

for (int p = i + 1; p <= j; p++) {    if (!canR[p]) continue;    int ein = (i + 1 > p - 1) ? 1 : E[i + 1][p - 1];    if (!ein) continue;    int cont = (p == j) ? 1 : CONT[p + 1][j];    if (!cont) continue;    vv = (vv + (ll)canL[i] * ein % MOD * cont) % MOD;}V[i][j] = (int)vv;

E[i][j] 表示“一对括号之间的内容物”，由四种互不重叠的形态相加得到：S（纯星）、V（完整序列）、SV（星 + 序列）、VS（序列 + 星）。四种形态首尾字符特征不同，因此同一字符串不会被两种形态同时统计：

ll ee = ((ll)h[i][j] + V[i][j]) % MOD;for (int x = i; x < j; x++)    if (h[i][x]) ee = (ee + (ll)h[i][x] * V[x + 1][j]) % MOD;for (int y = i + 1; y <= j; y++)    if (h[y][j]) ee = (ee + (ll)V[i][y - 1] * h[y][j]) % MOD;E[i][j] = (int)ee;

CONT[i][j] 表示“括号闭合之后接续的内容”，即在 V 前面再接一段星 S，要么直接是 V，要么是 S + V：

ll cc = V[i][j];for (int b = i; b < j; b++)    if (h[i][b]) cc = (cc + (ll)h[i][b] * V[b + 1][j]) % MOD;CONT[i][j] = (int)cc;

四、V/E/CONT 的转移细节

• V：枚举匹配位置 p，要求 canR[p] 为真，且内部 E、后续 CONT 均非空（p==j 时后续为空，视作 1）。
• E：h[i][j] 为真时贡献纯星 S；V[i][j] 贡献完整序列 V；Σ h[i][x]·V[x+1][j] 贡献 SV；Σ V[i][y-1]·h[y][j] 贡献 VS。四种互斥，不重不漏。
• CONT：V[i][j] 本身，加上 Σ h[i][b]·V[b+1][j]（在 V 前接一段星 S）。

其中 h[i][j] 表示 [i,j] 能否全为 * 且长度不超过 k，用 bad 前缀和 O(1) 判定：若 [i,j] 内不含非 * 字符（即 bad[j]-bad[i-1]==0）且长度 ≤k，则 h[i][j]=1。

五、用前缀和把判定压到 O(1)

bad[i] 记录前缀中“不能作 *”的位置个数（即 canStar 为假的位置）。那么 [i,j] 能否全是星，只取决于 bad[j]-bad[i-1] 是否为 0。h[i][j] 的预处理因此是常数时间，整体转移虽在 [i,j] 上各有一个 O(n) 的内层枚举（枚举 p、x、y、b），但状态总数是 O(n^2)，所以总复杂度为 O(n^3)。n=500 时整数运算量级约为 1.25×10^8，C++ 开启 O2 优化可稳定通过。

六、边界与易错点

• 空串不是合法序列，但 () 的内层空要算：当 i+1 > p-1（内部为空）时 E 取 1。
• 多算 (SVS)：规则只有 (A)、(SA)、(AS)，内部不能同时两侧夹星，否则答案偏大。
• ? 不是乘 3：每个 ? 最终只承担一种角色，用 canL/canR/canStar 的 0/1 指示相乘即可。
• k 限制 S 长度且 S 非空：h[i][j] 需满足 1 ≤ 长度 ≤ k。
• 负数修正：凡是“大减小”形式的区间求和，减法后都要 if (sum < 0) sum += MOD;。
• 最终答案是 V[1][n]：要求整个串本身就是一个完整规范的超级括号序列。

参考代码

#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef unsigned long long ull;const int MOD = 1000000007;int main(){    ios::sync_with_stdio(false);    cin.tie(0);    int n, k;    if (!(cin >> n >> k)) return 0;    string str;    cin >> str;    vector<int> canL(n + 2, 0), canR(n + 2, 0), canStar(n + 2, 0);    for (int i = 1; i <= n; i++) {        char c = str[i - 1];        canL[i] = (c == '(' || c == '?');        canR[i] = (c == ')' || c == '?');        canStar[i] = (c == '*' || c == '?');    }    vector<int> bad(n + 2, 0);    for (int i = 1; i <= n; i++) bad[i] = bad[i - 1] + (canStar[i] ? 0 : 1);    vector<vector<int> > h(n + 2, vector<int>(n + 2, 0));    for (int i = 1; i <= n; i++)        for (int j = i; j <= n; j++) {            int L = j - i + 1;            if (L > k) continue;            if (bad[j] - bad[i - 1] == 0) h[i][j] = 1;        }    vector<vector<int> > V(n + 2, vector<int>(n + 2, 0));    vector<vector<int> > E(n + 2, vector<int>(n + 2, 0));    vector<vector<int> > CONT(n + 2, vector<int>(n + 2, 0));    for (int len = 1; len <= n; len++)        for (int i = 1; i + len - 1 <= n; i++) {            int j = i + len - 1;            ll vv = 0;            for (int p = i + 1; p <= j; p++) {                if (!canR[p]) continue;                int ein = (i + 1 > p - 1) ? 1 : E[i + 1][p - 1];                if (!ein) continue;                int cont = (p == j) ? 1 : CONT[p + 1][j];                if (!cont) continue;                vv = (vv + (ll)canL[i] * ein % MOD * cont) % MOD;            }            V[i][j] = (int)vv;            ll ee = ((ll)h[i][j] + V[i][j]) % MOD;            for (int x = i; x < j; x++)                if (h[i][x]) ee = (ee + (ll)h[i][x] * V[x + 1][j]) % MOD;            for (int y = i + 1; y <= j; y++)                if (h[y][j]) ee = (ee + (ll)V[i][y - 1] * h[y][j]) % MOD;            E[i][j] = (int)ee;            ll cc = V[i][j];            for (int b = i; b < j; b++)                if (h[i][b]) cc = (cc + (ll)h[i][b] * V[b + 1][j]) % MOD;            CONT[i][j] = (int)cc;        }    cout << V[1][n] << "\n";    return 0;}

复杂度分析

• 时间：O(n^3)。状态总数 O(n^2)，每个状态上 V、E、CONT 各有一个 O(n) 的内层枚举，合计 O(n^3)。n=500 时整数运算约 1.25×10^8 次，C++ O2 实测远低于 1 秒的时间限制。
• 空间：O(n^2)。V、E、CONT、h 四个二维数组，每个 n×n，n=500 时约 4×500^2×4B ≈ 4MB，远低于 512MB 内存限制。