专栏文章

题解：P12671 「TFXOI Round 2」String

__Vector_
P12671题解参与者 2已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@mip1jcxe
此快照首次捕获于
2025/12/03 04:38
3 个月前
此快照最后确认于
2025/12/03 04:38
3 个月前
查看原文
本文给出在 询问非随机 情况下的做法。
本文的询问为“是否有长度为 l1l_1 的回文串，有长度为 l2l_2 的回文前缀”，与原题面有区别，请注意。
关于记号：子串 S[l,r]=SlSl+1…SrS[l,r]=S_lS_{l+1}\dots S_{r}
设 S[0,n]S[0,n] 为一长度为 n+1n+1 的回文子串
设还有一个从 mm 处开始、长度为 n+1n+1 的、且与 S[0,n]S[0,n] 本质不同的回文子串为 S[m,m+n]S[m,m+n]
在后续，我们会证明，若 m≤n4+C1m\le\frac{n}{4}+C_1，则下一个与 S[0,n]S[0,n] 和 S[m,m+n]S[m,m+n] 本质不同的长度为 n+1n+1 回文子串 S[o,o+n]S[o,o+n] 一定满足：o>n2+C2o> \frac{n}{2}+C_2。C1,C2C_1, C_2 为两个很小的常数（由于笔者懒得推）。
换而言之，长度为 nn 的本质不同子串的平均分布密度最大为 4n\frac{4}{n}。对于一个长度为 NN 的字符串，所有长度为 KK 的本质不同字符串的个数最多为 O(NK)O(\frac{N}{K})
对询问（是否有长度为 l1l_1 的回文串，有长度为 l2l_2 的回文前缀）去重后，考虑所有 l1l_1 相同的询问。对 PAM 上所有长度为 l1l_1 的本质不同回文子串，打上询问 tag l2l_2；在所有 ll 打完 tag 后，在 PAM fail 树上 dfs，跑长度为 l1l_1 的回文子串结点是否有长度 l2l_2 的父亲。每一个询问最多贡献 O(Nl1)O(\frac{N}{l_1}) 复杂度（由于只有 O(Nl1)O(\frac{N}{l_1}) 个本质不同的回文子串）。
最大化时间复杂度，对 QQ 个询问贪心的选 l1l_1 最小的。由于 l1l_1 最多只有 O(l1)O(l_1) 个本质不同的询问，选择所有的长度为 l1l_1 的询问带来的贡献为 O(l1)×O(Nl1)=O(N)O(l_1)\times O(\frac{N}{l_1})=O(N)；你最多能完全选取 q=O(Q)q=O(\sqrt{Q}) 个 l1l_1（1+2+⋯+q=Q1+2+\dots +q=Q, q(1+q)2=Q\frac{q(1+q)}{2}=Q），故总时间复杂度为 O(NQ)O(N\sqrt{Q})
设 S[0,n]S[0,n] 为一长度为 n+1n+1 的回文子串
设还有一个从 mm 处开始、长度为 n+1n+1 的、且与 S[0,n]S[0,n] 本质不同的回文子串为 S[m,m+n]S[m,m+n]
若 m≤n4+C1m\le\frac{n}{4}+C_1，则下一个与 S[0,n]S[0,n] 和 S[m,m+n]S[m,m+n] 本质不同的长度为 n+1n+1 回文子串 S[o,o+n]S[o,o+n] 一定满足：o>n2+C2o> \frac{n}{2}+C_2
下面不加说明的，所有的 mm 或 m′m' 均满足 m,m′≤n4+C1m, m'\le\frac{n}{4}+C_1
由于 S[m,m+n]S[m,m+n] 是回文串，则 S[2m,n]S[2m,n] 一定也是回文串。
S[2m,n]S[2m,n] 是 S[0,n]S[0,n] 的回文后缀，则 S[2m,n]S[2m,n] 是 S[0,n]S[0,n] 的回文 Border，则 S[0,2m−1]S[0,2m-1] 是 S[0,n]S[0,n] 的周期。该条的证明请参考 OI Wiki
这也说明，对于每一个回文串 S[m′,m′+n]S[m',m'+n]，对应到 S[0,n]S[0,n] 中一定有周期 S[0,2m′−1]S[0,2m'-1]；若 S[0,n]S[0,n] 有周期 S[0,2m′−1]S[0,2m'-1]，则 S[m′,m′+n]S[m',m'+n] 才可能是回文串。
记 S[0,n]S[0,n] 的最小周期为 pp，最小偶数周期 p′=p or 2pp'=p \text{ or } 2p。p′≤2m≤n2p'\le 2m\le \frac{n}{2}。设 p′=2Pp'=2P，则 P≤n4P\le \frac{n}{4}
根据 border 和周期的那一套性质，我们只有 S[P,P+n],S[2P,2P+n],…S[kP,kP+n]S[P,P+n], S[2P, 2P+n], \dots S[kP,kP+n] 才可能是回文串（对应有有周期 S[0,p′−1],S[0,2p′−1],…S[0,kp′−1]S[0,p'-1], S[0,2p'-1], \dots S[0, kp'-1]）。其中 kk 为满足 kp′=2kP≤nkp'=2kP\le n 的最大正整数。kPkP 有 kP>n2+C2kP>\frac{n}{2}+C_2，否则 (k+1)p′≤n(k+1)p'\le n。
对于一个 S[k′P,k′P+n]S[k'P, k'P+n]，k′>0k'>0，在 S[k′P,n]S[k'P,n] 亦有周期 p′=2Pp'=2P。考虑回文中心 n2+k′P≤n\frac{n}{2}+k'P\le n，这个周期 p′p' 成立的范围一定会经过回文中心。
在 S[0,n],S[P,P+n],S[2P,2P+n],…S[kP,kP+n]S[0,n], S[P,P+n], S[2P, 2P+n], \dots S[kP,kP+n] 之中，最多重复出现 22 个本质不同的回文串。若有 33 个以及上的本质不同回文串，则一定有两个 kk 的奇偶性相同，记为 k1,k2(k1<k2)k_1,k_2(k_1<k_2)，k2=k1+2μPk_2=k_1+2\mu P。由于他们在回文中心之前周期均为 2P2P，起始周期 S[k2P,k2P+2P−1]S[k_2P,k_2P+2P-1] 为 S[k1P,k1P+2P−1]S[k_1P, k_1P+2P-1] 中的某一周期中的一段，故起始周期相同，回文中心之前相同，对称过去两串也相同。
下一个出现的本质不同回文串的位置 oo 一定 o>KP>n2+C2o>KP>\frac{n}{2}+C_2
设 N,QN,Q 同阶，我们可以构造出这个复杂度上界的字符串和询问。
我们用字符集大小 ∣∑∗∣=∞|\sum^*|=\infty 说明。考虑构造 N\sqrt{N} 个长度为 N\sqrt{N} 的回文字符串，使得所有回文串中中间的字符各不相同。询问 l1=[2,N],l2=[1,l1)l_1=[2,\sqrt{N}], l_2=[1,l_1)，共 O(N)∼O(Q)O(N)\sim O(Q) 个询问，每个询问对复杂度的贡献为 O(N)O(\sqrt{N})（N\sqrt{N} 个长度为 l1l_1 的本质不同回文串），总复杂度为 O(QN)∼O(NQ)O(Q\sqrt{N})\sim O(N\sqrt{Q})。
当 ∣∑∗∣=26|\sum^*|=26 时，尽可能构造 N\sqrt{N} 个离中间字符最近的字符各不相同的字符串。这样可以最大化长度较小时的本质不同回文串 。由于不同回文字符串的增速是指数的，复杂度相同。

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...