CSP-S 2021 括号序列

这道题考场杀我 \(2.5h\)，写了两个错误算法，最后写了一个 \(O(n^4)\)，然后优化成 \(O(n^3)\) 了。

题意

一开始读错题了，写了一个多小时的错解。当时以为只要括号都匹配，* 在哪里无所谓，只要连续的不超过 \(k\) 就可以。

所以请务必好好读题，接下来解释一下题意，并且引出解题所需的定义:

如果有一个合法序列，这个序列左右两个端点是一对互相匹配的括号，将整个序列括起来，我们称之为 "完全合法序列"。也就是题目中，第三种情况的合法序列。

那么本题中合法情况可以这样描述:

由若干完全合法序列组成，相邻的完全合法序列之间可以有不超过 \(k\) 个 * 分隔。

那么根据本题的要求，合法的序列的左端或右端加上不超过 \(k\) 个 *，然后在外面加一对括号，就得到了一个完全合法序列。(特别注意，左右不能同时加，但是可以都不加)

特别地，在不超过 \(k\) 个 * 外直接加括号也是完全合法序列。

\(O(n^4)\) DP

我们设计状态 \(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;
}