弱双回文串统计

· · 个人记录

一个串为弱双回文串当且仅当能把这个串劈成两个回文串，回文串可以是空串。弱双回文串的另一种定义方式是将其放在一个环上，能找到一个对称轴使得环对称。

一个串有若干种合法的分裂方式，描述为表达方式。

若一个弱双回文串只有一种表达方式，则我们称其为本源弱双回文串。

结论：若一个弱双回文串有至少 2 种表达方式，则这个串一定能被表达为一个弱双回文串重复多遍的结果。

例如 abbabb 可以被表达为 (abb)^2。

证明：

这里同一个字母不代表表达的字符相同，只代表一个部分。

这个串的某两种表达方式为 A|? 和 ?|B，具体的写成

AAAAAA|????????? ?????

?????? ?????????|BBBBB

上下对应一下

AAAAAA|CCCCCCCCC BBBBB

AAAAAA CCCCCCCCC|BBBBB

翻转，设 C 翻转后为 D

AAAAAA|BBBBBDDDD DDDDD

DDDDDD DDDAAAAAA|BBBBB

出现了 (AB)D=D(AB) 的形式，根据弱周期定理，周期长度为 \gcd(|D|,|A|+|B|+|D|)。

但是我们还需要说明周期一定是弱双回文串，这里我们抛开弱周期定理。

注意到 AB 就是一个弱双回文串，且 AB 是原串的 Border，直接考虑通过归纳将这个证明转成一个更小弱双回文串的双表示法证明。

首先若 AB 就是原串的整周期，则证明结束；

否则找到一个形如 ABE=EAB 且 |AB|>|E| 的位置，进行分析：

仅保留 EAB 长度为 |AB| 的前缀，注意到 E 是 AB 的一个后缀，所以 EAB 的这个前缀一定是 AB 的循环位移，对应到弱双回文串的环定义上，循环位移后还是弱双回文串。于是我们找到了 AB 的两种表达方式，并且 |AB|<|ABD|，所以递归证明成立。

更进一步的，能发现如果一个弱双回文串不是本源弱双回文串，则它可以表达为一个本源弱双回文串重复若干遍的结果。

所以我们设长度为 n 的弱双回文串的划分方式的个数和为 F(n)，长度为 n 的本源弱双回文串个数为 G(n)，长度为 n 的弱双回文串个数为 A(n)，则有

G=F-G\times(Id-e) G\times Id=F A=G\times1=\dfrac{F\times1}{Id}=\dfrac{F}{\varphi}

所以统计弱双回文串的个数直接杜教筛即可。