P3449 [POI2006]PAL-Palindromes

· · 题解

Upd on 2022.9.3：换成更自然的推导方式。

*P3449 [POI2006]PAL-Palindromes

好题。

若 s_i + s_j 是回文串，因为 s_i, s_j 均回文，所以当 |s_j| < |s_i| 时，s_j 是 s_i 的前缀且 s_i[|s_j| + 1, |s_i|] 回文，当 |s_j| = |s_i| 时，s_i = s_j，当 |s_j| > |s_i| 时，s_i 是 s_j 的前缀且 s_j[|s_i | + 1, |s_j|] 回文。因此，对于任意长度不等的字符串无序对 s_i 和 s_j，若它们之间存在前缀关系，则对答案产生 2 的贡献。最后将答案加上 n 即可。

具体实现方法为枚举每个 s_i 的每一位 p(1\leq p < |s_i|)，求出 s_i[1, p] 在 s 中的出现次数，以及 s_i[p + 1, |s_i|] 是否是回文串。前者用字典树维护，后者用 Manacher 维护，可以做到时间复杂度线性，空间复杂度线性字符集。

实际上本题还有更巧妙的做法。

我们观察 x, y(|x| < |y|) 和 x + y，它们都是回文串。首先将 y 分成 p = y[1, |y| - |x|] 和 q = y[|y| - |x| + 1, |y|]，可知 q = x，则 x + y = xpx。因为 y 为回文串，所以 y 既然以 p 作为前缀，那么以 p 作为后缀，因此 y = px = px'p，x + y = x'p / px'p。又因为 x + y 关于最中间的 p 回文，所以 x'p 是回文串，可知 x' 有长为 p 的前缀。因此 x + y = px''p / ppx''p，再根据 y 为回文串推出 x + y = px'''pp / ppx'''pp，以此类推。简单地说，不断运用 y 和 x + y 为回文串的性质，可以推得 x 和 y 有相同的长度为 |y| - |x| 的 回文周期。

进一步地，我们发现若 回文串 a 有长为 |b| 的回文周期且 |b| \nmid |a|，则 a 有长为 |b| - |a| 的回文周期。推导过程是类似的：设 a = bbb \cdots bc，c 为 b 的前缀，c ^ R 表示 c 翻转后得到的串。

因为 a, b 均为回文串，所以 a = c ^ Rb \cdots bbb。

综合上述两点，可知 |c| 为 a 的回文周期。

不断应用上述结论，可知

若长度为 n 的 回文串 s 存在 回文 周期 p，则 s 存在长为 \gcd(n, p) 的 回文整周期。

结合辗转相减法和上述结论易证。

又因为 x 和 y 均有相同的长度为 |y| - |x| 的回文周期，且 \gcd(|x|, |y| - |x|) = \gcd(|y|, |y| - |x|)，得到 x, y 具有 完全相同的回文整周期，这是必要条件。反过来易证其充分性。

综上，KMP 求出每个字符串的 nxt 数组，反证法可证若 |s| - nxt_{|s|} 整除 |s| 则 s[1, |s|-nxt_{|s|}] 是最短回文整周期字符串，否则最短回文整周期字符串就是 s 本身。

每个本质不同的字符串对答案的贡献为 c ^ 2，其中 c 表示它作为 c 个串的最短回文整周期字符串。为此，排序并检查相邻两个最短回文周期字符串是否相等。时间复杂度线性对数。代码。

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define TIME 1e3 * clock() / CLOCKS_PER_SEC
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
inline int read() {
  int x = 0;
  char s = getchar();
  while(!isdigit(s)) s = getchar();
  while(isdigit(s)) x = x * 10 + s - '0', s = getchar();
  return x;
}
inline void print(int x) {
  if(x < 0) return putchar('-'), print(-x);
  if(x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
bool Mbe;
constexpr int N = 2e6 + 5;
int n, nxt[N];
char str[N];
string s[N];
bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  ios::sync_with_stdio(0);
  cin >> n;
  for(int i = 1; i <= n; i++) {
    int m;
    cin >> m >> str + 1;
    for(int j = 2, p = 0; j <= m; j++) {
      while(p && str[p + 1] != str[j]) p = nxt[p];
      nxt[j] = p += str[p + 1] == str[j];
    }
    if(m % (m - nxt[m]) == 0)
      for(int j = 1; j <= m - nxt[m]; j++)
        s[i] += str[j];
    else
      for(int j = 1; j <= m; j++)
        s[i] += str[j];
  }
  sort(s + 1, s + n + 1);
  ll ans = 0;
  for(int i = 1; i <= n; i++) {
    int r = i;
    while(r < n && s[r + 1] == s[i]) r++;
    ans += 1ll * (r - i + 1) * (r - i + 1);
    i = r;
  }
  cout << ans << "\n";
  cerr << TIME << " ms\n";
  return 0;
}
/*
2022/9/3
author: Alex_Wei
start coding at 6:58
finish debugging at 7:05
*/