题解 - Luogu P8256 [NOI Online 2022 入门组] 字符串

NOI 数据太水。

简述题意

给定操作序列 $S$ 和字符串 $T$。考虑这样的过程：维护一个初始为空的字符串 $R$，依次执行 $S$ 中的操作：若为 0 或 1 则在 $R$ 末尾加入此字符，否则为 - 就删去 $R$ 开头或末尾字符。求有多少种不同的方案，使得最终 $R$ 与 $T$ 相同。两方案不同当且仅当一次删除操作的方向不同。$|S|,|T|\le 400$。

分析

正向考虑这一过程，会首先想到维护字符串本身，再想办法刻画它与 $T$ 匹配的情形。感觉不简单，所以考虑反向操作。整个过程就变成：要对 $T$ 进行操作，让它最后为空。

于是发现删除操作会变成在头或尾加入一个任意字符，令它为 X。原先的 0 操作会变成删除末尾的 X 或 0，1 操作会变成删除末尾的 X 或 1。由于现在的删除只在末尾操作，发现不为 X 的部分必然为 $T$ 的一个前缀（可以为空）。所以当前字符串的状态就更易于刻画。

考虑动态规划计数。令 $f_{i,j,k}$ 表示做完了（正向）第 $i$ 次及其往后的操作，当前字符串开头有 $j$ 个 X，紧接着是 $T$ 的长度为 $k$ 的前缀。总长度可以预处理为 $l_i$，故末尾的 X 数量为 $l_i-j-k$。

初始状态：$f_{n,0,m}=1$。

对于 - 操作，前后各转移一次：

$$f_{i-1,j,k}:=f_{i-1,j,k}+f_{i,j,k}$$

$$f_{i-1,j+1,k}:=f_{i-1,j+1,k}+f_{i,j,k}$$

对于 0/1 操作：

当 $j+k\neq l_i$ 时，删除末尾的 X：

$$f_{i-1,j,k}:=f_{i-1,j,k}+f_{i,j,k}$$

否则在末字符匹配得上的条件下：

$$f_{i-1,j,k-1}:=f_{i-1,j,k-1}+f_{i,j,k}$$

一个在状态设计上的细节：对于 $k=0$ 的时候最好只转移一个 $j$，避免出现尴尬情况。以下钦定 $k=0$ 时 $j=0$。答案就是 $f_{0,0,0}$。

时间复杂度 $O(tn^2m)$，空间上可以使用滚动数组做到 $O(nm)$，这样做也极大优化了时间常数。

代码

#include <bits/stdc++.h>
using namespace std;

const int MXN = 405;
const int DVS = 1e9 + 7;
int T, N, M, len[MXN], cnt[2][MXN][MXN];
char ops[MXN], pat[MXN];

inline void add(int &x, int y) {
  if ((x += y) >= DVS) x -= DVS;
}

int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);
  cin >> T;
  while (T--) {
    cin >> N >> M >> ops >> pat;
    len[0] = 0;
    for (int i(0); i != N; ++i)
      len[i + 1] = len[i] + (ops[i] == '-' ? -1 : 1);
    if (len[N] != M) {
      cout << 0 << endl;
      continue;
    }
    memset(cnt[N & 1], 0, sizeof cnt[N & 1]);
    cnt[N & 1][0][M] = 1;
    for (int i(N); i >= 1; --i) {
      bool ii(i & 1);
      memset(cnt[!ii], 0, sizeof cnt[!ii]);
      if (ops[i - 1] == '-') {
        for (int j(0); j < len[i]; ++j) {
          for (int k(1); j + k <= len[i]; ++k) {
            add(cnt[!ii][j + 1][k], cnt[ii][j][k]);
            add(cnt[!ii][j][k], cnt[ii][j][k]);
          }
        }
        add(cnt[!ii][0][0], cnt[ii][0][0]);
        add(cnt[!ii][0][0], cnt[ii][0][0]);
      } else {
        for (int j(0); j < len[i]; ++j) {
          for (int k(1); j + k < len[i]; ++k) {
            add(cnt[!ii][j][k], cnt[ii][j][k]);
          }
          if (pat[len[i] - j - 1] == ops[i - 1])
            add(cnt[!ii][len[i] - j - 1 == 0 ? 0 : j][len[i] - j - 1],
                cnt[ii][j][len[i] - j]);
        }
        add(cnt[!ii][0][0], cnt[ii][0][0]);
      }
    }
    cout << cnt[0][0][0] << endl;
  }
  return 0;
}