题解 CF1394E 【Boboniu and Banknote Collection】

写得过于意识流了。

首先可以验证题面里给出的折叠定义是符合我们直觉的。

对于一个串，我们称其为Z的，当且仅当它能表示为 A\overline{A}A。其中 \overline{A} 表示 A 的反转串。

我们称一个非空字符串是本原Z的，当且仅当它是Z的且不包含Z真子串。

性质1:对于一个大串S，如果它的两个偶回文子串满足中心不重叠，且互相包含对方的中心，则该串一定包含一个Z子串。

证明可以考虑以这两个子串的中心为左右端点的子串，将该子串往左右翻转即得一个Z的子串。

推论1：任一本原Z串有唯一的回文前后缀。

性质2：一个大串S如果包含本原Z子串，那么一定存在一种最优方案，使得该子串恰好被沿着唯一的回文前后缀的中心折了两次。

证明的话，由于推论1，讨论一下折叠次数即可。

由性质2，我们可以不断寻找本原Z子串 A\overline{A}A 并将其替换为 A。从而我们仅需考虑不包含本原Z子串的串。

子问题：对于一个不包含本原Z子串的串，我们该如何求解？

性质1的推论2：任意一个不包含本原Z子串的串，其任意两个回文后缀的长度之比一定不小于2（大比小）。

于是如果此时答案大于0，则一定存在一次折叠是把原串的某个回文前后缀往里折。

我们暴力枚举这个前后缀并暴力递归，递归状态为区间[l,r]。

看起来状态数是 O(n^2) 的，但实际上，记该串长度为 n，最长回文前缀长度为d，可以发现所有出现过的左端点数量大致满足递归式 T(n)=T(d)+T(n/d)。

这是因为，首先对于回文后缀的递归不影响左端点数量可以忽略。然后，由推论2，可以认为所有出现过的左端点l被d分为两半，左半边是T(d)。右半边的话，应该可以给T加个角标 T_d(n) 表示头上接了长度为d的回文串后的可能左端点数量，应该可以归纳证明 T_d(n)=O(\log \frac{n}{d})。

毛估估一下就得到了 T(n)=O(\log n)，这也是符合实验结果的。

回到原题，实际上我们额外要做的事是push_back字符的同时维护将所有Z子串消掉的结果。由性质1，一个不包含本原Z子串的串，push_back一个字符后，至多在后缀处产生一个Z子串，删掉即可。

注意到这样得到的所有不包含本原Z子串的串构成一棵Trie,对于Trie上的任一节点执行暴力递归的过程，由前述文字可知到达过的左端点不超过 O(\log n)。再加上枚举回文前后缀的过程，总复杂度为 O(n\log^2n)。