CSP-S 2021 括号序列
比利♂海灵顿
2021-10-26 16:33:52
# CSP-S 2021 括号序列
这道题考场杀我 $2.5h$，写了两个错误算法，最后写了一个 $O(n^4)$，然后优化成 $O(n^3)$ 了。
## 题意
一开始读错题了，写了一个多小时的错解。当时以为只要括号都匹配，`*` 在哪里无所谓，只要连续的不超过 $k$ 就可以。
所以请务必好好读题，接下来解释一下题意，并且引出解题所需的定义:
如果有一个合法序列，这个序列左右两个端点是一对互相匹配的括号，将整个序列括起来，我们称之为 "完全合法序列"。也就是题目中，第三种情况的合法序列。
那么本题中合法情况可以这样描述:
由若干完全合法序列组成，相邻的完全合法序列之间可以有不超过 $k$ 个 `*` 分隔。
那么根据本题的要求，合法的序列的左端或右端加上不超过 $k$ 个 `*`，然后在外面加一对括号，就得到了一个完全合法序列。(特别注意，左右不能同时加，但是可以都不加)
特别地，在不超过 $k$ 个 `*` 外直接加括号也是完全合法序列。
## $O(n^4)$ DP
> 这里 $k$ 作为循环枚举的变量，所以用 $m$ 表示题目中要求最多的连续的 `*` 的数量。
我们设计状态 $f_{Len, i}$ 表示以 $i$ 为左端点，长度为 $Len$ 的区间为完全合法序列的方案数，$g_{Len, i}$ 表示以 $i$ 为左端点，长度为 $Len$ 的区间为合法序列的方案数。
首先发现任何合法的序列，其左右两端一定分别是 `(` 和 `)`，所以当输入序列左端点是 `*` 或 `)` 或右端点是 `*` 或 `(` 时，两个值都为 $0$。
两端点合法后，考虑转移:
$$
f_{Len, i} = g_{Len - 2, i + 1} + \sum_{j = 1}^{min(Len - 2, m)} g_{Len - 2 - j, i + 1 + j} + \sum_{k = 1}^{min(Len - 3, m)}g_{Len - 2 - k, i + 1}
$$
第一个转移表示直接在合法序列外加括号，第二个和第三个表示在合法序列的左边或右边加若干 `*` 后再加括号。
其中 $j$ 枚举过程中需要考虑区间 $[i + 1, i + j]$ 必须都是 `*` 或 `?`，否则直接 `break`。$k$ 也是一样的，枚举过程中判断当前位置是否可以变成 `*`。
至于为什么 $k \leq min(Len - 3, m)$，因为对于 $j = Len - 2$ 的情况，表示的是直接在连续的 `*` 外面加括号，如果 $k = Len - 2$ 再统计一次，就会重复统计。
接下来是 $g$ 的转移:
$$
g_{Len, i} = \sum_{j = 0}^{Len - 2} (g_{j, i} * \sum_{k = 0}^{min(Len - j - 2, m)} f_{Len - j - k, i + j + k})
$$
这里的转移表示先选一个长度为 $j$ 的合法序列 $[i, i + j - 1]$，然后在它后面加 $k$ 个 `*`，后面再接一个长度 $Len - j - k$ 的完全合法序列，组成一个新的合法序列。
当然，这里枚举 $k$ 的时候也要判断对应位置是否能赋成 `*`，否则 `break`。
枚举边界两个 $-2$ 是因为完全合法序列最短也要 $2$，所以要提前留至少两个长度给最后的完全合法序列。
答案便是 $g_{n, 1}$。
两个 DP 状态都是 $O(n^2)$，$f$ 的转移是 $O(n)$，$g$ 的转移是 $O(n^2)$，总复杂度 $O(n^4)$。
复杂度里面有一个 $n$ 是和连续的 `*` 的数量有关的，所以随机数据下 $O(n^4)$ 跑 $500$ 飞快。
## 优化到 $O(n^3)$
发现算法的瓶颈在于转移 $g$ 的时候，枚举中间的 `*` 的数量。
这时候，增加一个状态 $g_{Len, i, 0}$ 表示的信息和之前的 $g$ 相同，加一个 $g_{Len, i, 1}$ 表示这个区间内，除去右端的 $(0, m]$ 个 `*`，左边留下的是非空的合法序列的方案数。
这个状态不是一般的好求
$$
g_{Len, i, 1} = \sum_{j = 1}^{min(Len - 2, m)} g_{Len - j, i, 0}
$$
转移意义为在合法序列后加 $j$ 个 `*`。
这个 $j$ 枚举时仍要判断对应位置是否能取 `*`，否则 `break`。
然后就可以把 $g_{Len, i, 0}$ 的转移优化到 $O(n)$。
$$
g_{Len, i, 0} = \sum_{j = 0}^{Len - 2} ((g_{j, i, 0} + g_{j, i, 1}) * f_{Len - j, i + j}))
$$
转移表示合法序列还是合法序列后加 $(0, m]$ 个 `*`，这些情况后面加完全和法序列，一定能得到合法序列。
总复杂度优化到了 $O(n^3)$。
而且这时 $f$ 的转移也简化了。
$$
f_{Len, i} = g_{Len - 2, i + 1, 0} + g_{Len - 2, i + 1, 1} + \sum_{j = 1}^{min(Len - 2, m)} g_{Len - 2 - j, i + 1 + j, 0}
$$
接下来是去掉缺省源的考场代码:
```cpp
unsigned long long Mod(1000000007);
unsigned long long f[505][505], g[505][505][2];
unsigned n, m;
unsigned A, B, C, D;
unsigned Cnt(0), Ans(0), Tmp(0);
char a[505];
signed main() {
n = RD(), m = RD();
scanf("%s", a + 1);
for (unsigned i(n); i; --i) g[0][i][0] = f[0][i] = 1;
for (unsigned Len(2); Len <= n; ++Len) {
for (unsigned i(n - Len + 1); i; --i) {
for (unsigned len(1); len < Len && len <= m; ++len) {
if((a[i + Len - len] == '(') || (a[i + Len - len] == ')')) break;
g[Len][i][1] += g[Len - len][i][0];
if(g[Len][i][1] >= Mod) g[Len][i][1] -= Mod;
}
if((a[i] == '*') || (a[i] == ')') || (a[i + Len - 1] == '*') || (a[i + Len - 1] == '(')) {
continue;
}
unsigned Tol(min(Len - 2, m));
f[Len][i] = g[Len - 2][i + 1][0] + g[Len - 2][i + 1][1];
if(f[Len][i] >= Mod) f[Len][i] -= Mod;
for (unsigned len(1); len <= m && len + 2 <= Len; ++len) {
if((a[i + len] == '(') || (a[i + len] == ')')) break;
f[Len][i] += g[Len - 2 - len][i + len + 1][0];
if(f[Len][i] >= Mod) f[Len][i] -= Mod;
}
g[Len][i][0] = f[Len][i];
for (unsigned len(2); len + 2 <= Len; ++len) {
g[Len][i][0] = (g[Len][i][0] + g[len][i][1] * f[Len - len][i + len]) % Mod;
}
for (unsigned len(2); len + 2 <= Len; ++len) {
g[Len][i][0] = (g[Len][i][0] + g[len][i][0] * f[Len - len][i + len]) % Mod;
}
}
}
printf("%llu\n", g[n][1][0]);
return 0;
}
```