CSP-S 2021 括号序列

· · 题解

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}

接下来是去掉缺省源的考场代码:

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;
}