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
", g[n][1][0]);
	return 0;
}