这个数组相当于记忆化搜索,当我们要从 p 节点为了找 c 字符时开始跳,这个结果可以记作 get_{p, c}。每次新建节点 p 时,从 fail 树上的父亲继承 get 数组,然后用 p \to fail_p 更新 get_p 即可。这样我们用类似 DP 的方式存下了跳链的结果,也就变成了 O(\sum) - O(1)。
Q: $ 我们跳链是为了找左边有一个字符 $c$ 的回文子串,但是左边有什么跟这个串本身又没有关系,而是跟 $s$ 相关,如何保证记下来的 $get$ 是通用的? $\\
对 $get$ 数组做可持久化就得到了可持久化 PAM。
---
# 例题
为了更好地理解这部分知识点,我会把独属于每个题的分析问题性质部分(称 A 部分)和上文提到的通用的字符串知识点和优化部分(称 B 部分)拆开,最后还会给出具体的细节实现(称 C 部分)。
## P1393(容斥 DP + $O(\log)$ 段等差 $border$)
> 求 $n \ (\leq 2 \times 10^5)$ 长度随机生成的字符串包含给定字符串 $s$ 的概率。
### Part A
令 $f_i$ 表示 $[i - |s| + 1, i]$ 这些字符恰好是 $s$,且前面从来没有出现 $s$ 的方案数,不难容斥做到 $O(n^2)$。
### Part B
你把代码写出来就能知道,刚刚容斥的瓶颈是枚举 $border$,但是它们构成了 $O(\log |s|)$ 个等差数列,因此记 $O(\log |s|)$ 份前缀和就能优化了。
### Part C
```cpp
/* Good Game, Well Play. */
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;
const int N = 200010, mod = 998244353;
inline long long qpow(long long a, long long b)
{long long res = 1; while(b) {if(b & 1) res = res * a % mod; b >>= 1, a = a * a % mod;} return res;}
int n, k, m, s[N], nxt[N], w[N], wn; long long f[N], pw[N], pwi[N];
inline void get(int len) {if(!len) return ; w[++wn] = m - len, get(nxt[len]);}
long long p[110][N];
struct Seq {int x, d, lim;} seq[110]; int sn;
inline long long S(int id, int l, int r)
{if(r <= 0) return 0; l = max(l, 0); return (p[id][r] - p[id][l] + mod) % mod;}
int main()
{
// freopen("text.in", "r", stdin);
// freopen("prog.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> k >> m;
for(int i = 1; i <= m; ++i) cin >> s[i];
pw[0] = 1; for(int i = 1; i <= n; ++i) pw[i] = pw[i - 1] * k % mod;
pwi[0] = 1; for(int i = 1, iv = qpow(k, mod - 2); i <= n; ++i) pwi[i] = pwi[i - 1] * iv % mod;
for(int i = 2; i <= m; ++i)
{
nxt[i] = nxt[i - 1];
while(nxt[i] && s[nxt[i] + 1] != s[i]) nxt[i] = nxt[nxt[i]];
if(s[nxt[i] + 1] == s[i]) ++nxt[i];
}
get(nxt[m]);
for(int l = 1; l <= wn; ++l)
{
int r = l + 1;
if(l == wn) seq[++sn] = {w[l], 1, 0};
else
{
while(r < wn && w[r + 1] - w[r] == w[r] - w[r - 1]) ++r;
seq[++sn] = {w[l], w[l + 1] - w[l], r - l}; l = r;
}
}
for(int i = m; i <= n; ++i)
{
f[i] = pw[i - m];
f[i] = (f[i] - p[0][i - m] * pw[i - m] % mod + mod) % mod;
for(int j = 1; j <= sn; ++j)
f[i] = (f[i] - S(j, i - seq[j].x - seq[j].d * (seq[j].lim + 1), i - seq[j].x) + mod) % mod;
p[0][i] = (p[0][i - 1] + f[i] * pwi[i]) % mod;
for(int j = 1; j <= sn; ++j) p[j][i] = (p[j][max(0, i - seq[j].d)] + f[i]) % mod;
}
long long res = 0;
for(int i = m; i <= n; ++i) res = (res + f[i] * pw[n - i]) % mod;
cout << res * qpow(pwi[1], n) % mod << '\n';
return 0;
}
/*
*/
```
## P5287(Ad-hoc + $O(\log)$ 段等差 $border$)
> 写一个程序,要求支持加入 $x$ 个相同字符以及回退版本,并在每次操作后求出 $\sum nxt$。不要求可持久化,允许离线。
### Part A
因为不要求可持久化,所以回退版本并不是什么难点,建出操作树或者直接暴力删都是可以的。问题在于如何维护加字符操作。我们知道若两串字符相等,除了首尾两部分,把剩下的二元组 $(x, c)$ 看成单个**压缩字符**,它们组成的字符串应该也是完全相等的。不妨对压缩字符做 KMP。边跳 $nxt$ 边计算贡献。
计算贡献的部分可以参考我的代码,
### Part B
回滚 ban 掉了均摊复杂度,算贡献 ban 掉了 KMP 自动机,但是我们还有一条路,即运用 $O(\log)$ 段等差数列性质。
这个性质的由来是字符串的周期,那么一段等差 $border$ 对应的前缀后面接的字符串都有一段 LCP,即这个周期。周期至少有一个压缩字符,则它们对答案的贡献一致,可以直接跳过,跳到大于周期 $t$ 的最小 $border$。
这样暴力跳 $nxt$ 的复杂度变为严格 $O(\log n)$,可以通过。
### Part C
加了注释。
```cpp
/* Good Game, Well Play. */
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;
const int N = 100010, mod = 998244353;
int n, ver[N]; long long res[N];
struct Edge {int to, x; char c;}; vector < Edge > tr[N]; int idx = 1;
struct Char {int x, c;} s[N]; int len, prx[N], nxt[N];
inline bool find_son(int p, int x, int c)
{
if(!p) return (s[p + 1].c == c && s[p + 1].x <= x); // 如果在字符串的开头,那么开头少几个字符也是可以匹配上的,只要 x 个字符不全用完就行了
else return (s[p + 1].c == c && s[p + 1].x == x); // 不然必须要求 (x, c) 二元组相等
}
inline int get_sum(int l, int r)
{if(l > r) return 0; return 1ll * (l + r) * (r - l + 1) / 2 % mod;}
inline int insert(int x, char c)
{
s[++len] = {x, c}; prx[len] = prx[len - 1] + s[len].x;
if(len == 1) return get_sum(1, x - 1); // 同 KMP 和 Z 函数理,len = 1 需要特判
int p = nxt[len - 1], lst = len, maxlen = 0; long long delt = 0;
// 这里记录 maxlen 的意思是,当前有 x 个字符等着算贡献,因为要找最大 border,所以贪心把前面能找的都找了,后面的以后再去找
while(p && !find_son(p, x, c))
{
if(s[p + 1].c == c && min(x, s[p + 1].x) > maxlen)
{
delt = (delt + get_sum(prx[p] + maxlen + 1, prx[p] + min(x, s[p + 1].x)));
maxlen = s[p + 1].x;
}
if(lst - p == p - nxt[p])
{
int t = p - nxt[p];
lst = p; p = p % t + t;
}
else lst = p, p = nxt[p];
}
if(find_son(p, x, c))
{
nxt[len] = p + 1;
delt = (delt + get_sum(prx[p] + maxlen + 1, prx[p] + s[p + 1].x));
delt = (delt + 1ll * s[p + 1].x * (x - max(maxlen, s[p + 1].x))); // 这是针对匹配到开头,x 个字符不全用完所补加的贡献
}
else
{
nxt[len] = p;
if(s[p + 1].c == c && min(s[p + 1].x, x) > maxlen)
delt = (delt + get_sum(maxlen + 1, maxlen + min(s[p + 1].x, x)));
}
return delt;
}
inline void roll()
{
s[len] = {0, 0}; prx[len] = nxt[len] = 0;
--len;
}
inline void solve(int now)
{
for(Edge li : tr[now])
{
res[li.to] = (res[now] + insert(li.x, li.c)) % mod;
solve(li.to); roll();
}
}
int main()
{
// freopen("text.in", "r", stdin);
// freopen("prog.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n; ver[0] = 1;
for(int i = 1, p = 1; i <= n; ++i)
{
int op, x; char c; cin >> op;
if(op == 1)
{
cin >> x >> c;
++idx; tr[p].push_back({idx, x, c});
p = idx; ver[i] = p;
}
else
{
cin >> x;
ver[i] = p = ver[x];
}
}
solve(1);
for(int i = 1; i <= n; ++i) cout << res[ver[i]] << '\n';
return 0;
}
/*
*/
```
## P4156(同余最短路 + $O(\log)$ 段等差 $border$)
> 给定一个字符串 $s$,你有一个串 $t$,初始为空,可以反复做以下操作:
>
> - 在 $t$ 后面接上一段长度不超过 $|s|$ 的字符,使得 $t$ 的最后 $|s|$ 个字符等于 $s$。
>
> 求 $t$ 的**长度**在 $m$ 范围内的可能数量,$m \leq 10^{18}$。
### Part A
可见扩展一次的长度总是 $|s| - k$,其中 $k$ 是某个 $border$ 的长度。
则所求的是值域为 $m$,元素个数 $O(|s|)$ 个的可行性完全背包。稍微优化一下,同余最短路也是做这个问题的。
### Part B
运用关键性质:$O(n)$ 个元素实际上构成了 $O(\log n)$ 段等差数列,因此对每段等差数列 $x, x + t, x + 2t, \dots, x + yt$ 分别算同余最短路,中间涉及到每次更新和更换模数两个问题。
以上面的 $x$ 作为模数,则所有 $p \to (p + t) \bmod x$ 的边构成若干个环,环内的 $p$ 可以在不超过走 $y$ 次 $p \to (p + t) \bmod x$ 的边的情况下更新所达到的点,可以单调队列维护。
更换模数时,设当前模数是 $x$,上次是 $x'$,首先得做一个 $p \to f_p \bmod x$,然后还要 $p \to (p + x') \bmod x$,此时没有最多 $y$ 次的限制,不需要单调队列了。
### Part C
实现难度主要在于同余最短路,建议先学习 P3403 模板题,会了那个题的思想后写起来很快。
```cpp
/* Good Game, Well Play. */
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;
const int N = 500010;
int T, n, nxt[N], w[N], wn; long long m; string s;
inline void get(int len) {w[++wn] = n - len; if(len) get(nxt[len]);}
struct Data {int id; long long num;}; deque < Data > dq;
long long f[N], tmp[N]; int lst; bool vis[N];
inline void refresh(int mod, int d, int lim)
{
// cerr << "refresh " << mod << " " << d << " " << lim << '\n';
if(lst == 0)
{
for(int i = 0; i < mod; ++i) f[i] = m + 1;
f[n % mod] = n;
}
else
{
for(int i = 0; i < mod; ++i) tmp[i] = m + 1;
for(int i = 0; i < lst; ++i) tmp[f[i] % mod] = min(tmp[f[i] % mod], f[i]);
for(int i = 0; i < mod; ++i) vis[i] = false;
for(int i = 0; i < mod; ++i)
{
if(vis[i]) continue;
int p = i, mnp = -1; long long comp = m + 10; vector < int > rec;
do {if(tmp[p] < comp) comp = tmp[p], mnp = p; p = (p + lst) % mod;} while(p != i);
p = mnp; while(!vis[p]) {vis[p] = true; rec.push_back(p); p = (p + lst) % mod;}
comp = m + 10;
for(int j = 1; j < rec.size(); ++j)
tmp[rec[j]] = min(tmp[rec[j]], tmp[rec[j - 1]] + lst);
}
for(int i = 0; i < mod; ++i) f[i] = tmp[i];
}
// cerr << "current f : "; for(int i = 0; i < mod; ++i) cerr << f[i] << " "; cerr << '\n';
lst = mod;
for(int i = 0; i < mod; ++i) vis[i] = false;
for(int i = 0; i < mod; ++i)
{
if(vis[i]) continue;
int p = i, mnp = -1; long long comp = m + 10; vector < int > rec;
do {if(f[p] < comp) comp = f[p], mnp = p; p = (p + d) % mod;} while(p != i);
p = mnp; while(!vis[p]) {vis[p] = true; rec.push_back(p); p = (p + d) % mod;}
dq.clear(); dq.push_back({0, f[rec[0]]});
for(int j = 1; j < rec.size(); ++j)
{
while(!dq.empty() && j - dq.front().id > lim) dq.pop_front();
f[rec[j]] = min(f[rec[j]], dq.front().num + j * d + mod);
Data cur = {j, f[rec[j]] - j * d};
while(!dq.empty() && dq.back().num >= cur.num) dq.pop_back();
dq.push_back(cur);
}
}
// cerr << "final f : "; for(int i = 0; i < mod; ++i) cerr << f[i] << " "; cerr << '\n';
}
inline void sol()
{
cin >> n >> m; lst = 0;
cin >> s; s = ' ' + s;
for(int i = 2; i <= n; ++i)
{
nxt[i] = nxt[i - 1];
while(nxt[i] && s[nxt[i] + 1] != s[i]) nxt[i] = nxt[nxt[i]];
if(s[nxt[i] + 1] == s[i]) ++nxt[i];
}
wn = 0; get(nxt[n]);
// cerr << "w : "; for(int i = 1; i <= wn; ++i) cerr << w[i] << " "; cerr << '\n';
for(int l = 1; l <= wn; ++l)
{
int r = l + 1;
if(l == wn) refresh(w[l], 0, 0);
else
{
while(r < wn && w[r + 1] - w[r] == w[r] - w[r - 1]) ++r;
refresh(w[l], w[l + 1] - w[l], r - l); l = r;
}
}
long long res = 0;
for(int i = 0; i < lst; ++i)
if(f[i] <= m)
res += 1 + (m - f[i]) / lst;
cout << res << '\n';
}
int main()
{
// freopen("text.in", "r", stdin);
// freopen("prog.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> T;
while(T--) sol();
return 0;
}
/*
*/
```
## P5555(PAM)
### Part A
无。
### Part B
走相同的转移边得到的回文串是一样的,可以同时在两个 PAM 上 DFS。
### Part C
DFS 部分:
```cpp
int res, cnt;
inline void search(int x, int y)
{
if(!x || !y) return ;
if(pam[0].len[x] > res) res = pam[0].len[x], cnt = 0;
if(pam[0].len[x] == res) ++cnt;
for(int i = 1; i <= 26; ++i) search(pam[0].son[x][i], pam[1].son[y][i]);
}
```
## CF932G(DP + PAM + $O(\log)$ 段回文)
> 求把 $s$ 划分成若干段的方案数,满足若段数为 $k$,总有 $s'_i = s'_{k - i + 1}$。
### Part A
设原字符串为 $\overline{s_1 s_2 \dots s_n}$,把它变为 $\overline{s_1 s_n s_2 s_{n - 1} \dots s_{\frac{n}{2} + 1}}$,则原问题变为划分为若干偶数回文段的方案数。
### Part B
这部分是必须掌握的经典问题,详见 [OI Wiki 相关部分](https://oi-wiki.org/string/pam/#%E4%BC%98%E5%8C%96)。
给点补充:
$Q_1 :$ $f, g$ 数组是依托什么设定的?$g$ 是 DP 数组吗?影响 $g$ 的是 $i$ 的变化还是 PAM 中的跳指针?$\\
$Q_2 :$ 既然 $g$ 数组的下标对应的是 PAM,那么它为什么可以精准地贡献到 $f_i$ 上?$\\
### Part C
提示:如果调试不出来,先考虑是 PAM 写错了,然后再看 DP 过程。
和这个题相似的还有 CF906E,基本上是双倍经验,能默写出其中一道题的代码就都能轻松通过。
加注释的代码。
```cpp
/* Good Game, Well Play. */
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;
const int N = 1000010, mod = 1e9 + 7;
int n; string s, org;
struct PAM
{
int son[N][27], tr[N][27], fail[N], len[N], dif[N], slink[N], idx, p;
inline void init() {p = idx = 2; fail[2] = 1; len[1] = -1, len[2] = 0;}
inline void insert(int pos, char c) // 这里采用的是严格 O(字符集大小) 的 PAM 实现,也可以用均摊 O(1) 的实现。
{
if(pos - len[p] - 1 <= 0 || s[pos - len[p] - 1] != c) p = max(1, tr[p][c - 'a' + 1]);
if(!son[p][c - 'a' + 1])
{
fail[++idx] = max(2, son[max(1, tr[p][c - 'a' + 1])][c - 'a' + 1]);
len[idx] = len[p] + 2, dif[idx] = len[idx] - len[fail[idx]];
if(dif[idx] == dif[fail[idx]]) slink[idx] = slink[fail[idx]]; // slink 指向上一个等差数列的最后一项
else slink[idx] = fail[idx];
son[p][c - 'a' + 1] = idx;
memcpy(tr[idx], tr[fail[idx]], sizeof(tr[idx]));
tr[idx][s[pos - len[fail[idx]]] - 'a' + 1] = fail[idx];
}
p = son[p][c - 'a' + 1];
}
}; PAM pam;
long long f[N], g[N];
int main()
{
// freopen("text.in", "r", stdin);
// freopen("prog.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> org; n = org.length(); org = ' ' + org; s = " ";
for(int i = 1; i <= n / 2; ++i) s += org[i], s += org[n - i + 1];
if(n % 2 == 1) {cout << 0 << '\n'; return 0;}
pam.init(); f[0] = 1;
for(int i = 1; i <= n; ++i)
{
pam.insert(i, s[i]);
for(int pt = pam.p; pt >= 3; pt = pam.slink[pt])
{
g[pt] = f[i - pam.len[pam.slink[pt]] - pam.dif[pt]]; // 这是 g[pt] 和 g[fail[pt]] 之间的差值,OI Wiki 中已说明
if(pam.slink[pt] != pam.fail[pt]) // 注意判断 fail 树上的父亲与自己不在同一个等差数列的情况
g[pt] = (g[pt] + g[pam.fail[pt]]) % mod;
if(i % 2 == 0) f[i] = (f[i] + g[pt]) % mod; // 由于必须划分为偶回文串,因此 i 是 2 的倍数是转移
}
}
cout << f[n] << '\n';
return 0;
}
/*
*/
```
## QOJ5037(线段树 + $O(\log)$ 段回文)
> 在支持单点修改字符的情况下求给定字符串 $s$ 的一个子串 $s_{[l, r]}$ 的回文后缀数量,强制在线。
很有操作的一道题。设 $X$ 的 $k$ 次方表示字符串 $X$ 重复 $k$ 次得到的结果,$X'$ 表示 $X$ 翻转得到的字符串。特别的,$X^0$ 为空串。
### Part A
这个题带修带查,还强制在线,显然不能 PAM 做了。但是无论字符串如何变化,$O(\log |s|)$ 段回文的性质都是在的,不妨像动态 DP 一样,把字符串挂到线段树上面,并维护 $[l, r]$ 的回文前缀和后缀。因为等差性,要记录的信息是 $O(\log(r - l + 1))$ 量级的。
### Part B
既然维护回文前缀和后缀是同一个方式,我们只分析维护后缀的方法。现已知线段树上 $[l, mid], (mid, r]$ 节点的回文前后缀,尝试得到 $[l, r]$ 的回文后缀信息。
这里免不了分类讨论:
#### Case I 回文后缀在 $(mid, r]$ 中
这部分可以继承 $(mid, r]$ 节点的信息,他们显然是等价的。
#### Case II 回文后缀跨过 $mid$,且中线在 $(mid, r]