P10047 [CCPC 2023 北京市赛] 勿蹖宠物

· · 题解

P10047 [CCPC 2023 北京市赛] 勿蹖宠物

对每个回文串，考虑它如何被统计入答案。如果只是单侧添加单词，则 DP 过程中难以满足回文的要求。考虑往两侧添加单词，哪一侧长度更短就往哪一侧加入单词，长度相同则规定往左边加入单词。

为了满足回文的限制，记录必要信息，设计 DP f_{0 / 1, i, j, k} 表示当前状态是左侧更长还是右侧更长，较短的一侧长度为 i，较长的一侧（从边界开始数）第 i + 1 个字符是第 j 个字符串的第 k 个字符，基于这些信息可以确定回文串已经匹配了左右两侧多少个字符，以及除去左右两侧匹配的 i 个字符之后剩余部分的具体形态。注意 (j, k) 状态总数为 S = \sum |s_i|。

转移即枚举要放的一侧放哪个字符串，判定合法性需要预处理 s_i 在 s_j 中的所有出现位置，以及 s_i 的每个前缀和 s_j 对应长度的后缀是否相等。时间复杂度 \mathcal{O}(nLS + S ^ 2)。

细节太多不想写怎么办？考虑从外往里依次确定每个字符，需要记录匹配长度，以及左右两侧分别匹配到哪个字符串的第几个字符。若某一侧刚好匹配完，则这一侧需要枚举新的字符串。时间复杂度 \mathcal{O}(L(n + S) ^ 2)，但代码非常好写。

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

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdi = pair<double, int>;
using pdd = pair<double, double>;
using ull = unsigned long long;
using LL = __int128_t;

#define ppc(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)

bool Mbe;

constexpr int mod = 1e9 + 7;
void addt(int &x, int y) {
  x += y, x >= mod && (x -= mod);
}
int add(int x, int y) {
  return x += y, x >= mod && (x -= mod), x;
}

// ---------- templates above ----------

constexpr int N = 600 + 5;

pii pos[N], vk[N], vl[N];
int n, L, cnt, lb[N][N];
int f[N][N], g[N][N];
string s[N];
void solve() {
  cin >> n >> L;
  for(int i = 1; i <= n; i++) {
    cin >> s[i];
    for(int j = 0; j + 1 < s[i].size(); j++) {
      pos[++cnt] = {i, j};
      lb[i][j] = cnt;
    }
  }
  f[0][0] = 1;
  for(int p = 0; p < L / 2; p++) {
    memset(g, 0, sizeof(g));
    int tot = 0;
    for(int i = 0; i <= cnt; i++) {
      for(int j = 0; j <= cnt; j++) {
        if(!f[i][j]) continue;
        int pk = 1, pl = 1;
        if(i) vk[0] = {pos[i].first, pos[i].second + 1};
        else {
          pk = n;
          for(int p = 1; p <= n; p++) vk[p - 1] = {p, 0};
        }
        if(j) vl[0] = {pos[j].first, pos[j].second - 1};
        else {
          pl = n;
          for(int p = 1; p <= n; p++) vl[p - 1] = {p, int(s[p].size()) - 2};
        }
        tot += pk * pl;
        for(int _k = 0; _k < pk; _k++) {
          for(int _l = 0; _l < pl; _l++) {
            pii k = vk[_k], l = vl[_l];
            int idk = k.first, pk = k.second, sk = lb[idk][pk];
            int idl = l.first, pl = l.second + 1, sl = pl ? lb[idl][pl - 1] : 0;
            if(s[idk][pk] == s[idl][pl]) addt(g[sk][sl], f[i][j]);
          }
        }
      }
    }
    swap(f, g);
  }
  int ans = 0;
  if(L & 1 ^ 1) {
    for(int i = 0; i <= cnt; i++) addt(ans, f[i][i]);
  }
  else {
    for(int i = 1; i <= n; i++) {
      if(s[i].size() == 1) addt(ans, f[0][0]);
      else {
        addt(ans, f[lb[i][s[i].size() - 2]][0]);
        addt(ans, f[0][lb[i][0]]);
        for(int j = 1; j < s[i].size() - 1; j++) {
          addt(ans, f[lb[i][j - 1]][lb[i][j]]);
        }
      }
    }
  }
  cout << ans << "\n";
}

bool Med;
signed main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  int T = 1;
  while(T--) solve();
  fprintf(stderr, "%.3lf ms\n", 1e3 * clock() / CLOCKS_PER_SEC);
  return 0;
}

/*
g++ a.cpp -o a -std=c++14 -O2 -DALEX_WEI
*/