ARC077F

https://www.luogu.com.cn/problem/AT_arc077_d

我们设 $T_i$ 表示 $f^i(S)$ 的前一半，例如输入的 $S=S'S'$，则 $T_0=S'$。

设 $B(T)$ 表示 $T$ 最长的不为自身的 border，则容易证明 $T_i = T_{i-1}T_{i-1}-B(T_{i-1})$，这里减法表示去除一个后缀。

我们证明如下结论：

• 如果 $S'$ 存在整周期，设其中最小的为 $X^k=S'$，因为如果存在整周期，则最小周期一定为最小整周期，于是 $T_i=X^{k+i}$。
• 如果 $S'$ 不存在整周期，设 $T_{i-1}=S'-B(S')$，则有 $\forall \ge 1,\ T_i = T_{i-1}T_{i-2},\ T_{i-2}=B(T_{i})$。

我们归纳证明第二种情况：

对于 $i=1$ 由定义可知第一部分成立。

当 $i=k$ 时第一部分成立时：

$T_{i-2}$ 一定是 $T_i=T_{i-2}T_{i-3}T_{i-2}$ 的一个 border，我们只需要证明它是最长的，否则设最长 border 为 $C$，如果 $|C|>|T_{i-2}T_{i-3}|$，则 $T_{i}$ 有长度小于 $T_{i-2}$ 的周期，则它的前缀 $T_{i-1}=T_{i-2}T_{i-3}$ 有长度超过 $T_{i-3}$ 的 border，与假设矛盾。

如果 $|T_{i-2}| \lt |C| \le |T_{i-2}T_{i-3}|$，设 $C=T_{i-2}A$，则 $A$ 是 $T_{i-3}$ 的前缀，所以它也是 $T_{i-2}$ 的前缀，也就是 $C$ 的 border，而 $T_{i-2}$ 也是 $C$ 的 border，因为 $|C|-|A|+|C|-|T_{i-2}| = |C|$，所以由弱周期引理得 $C$ 的长度为 $\gcd(|C|-|T_{i-2}|,|C|-|A|)=\gcd(|A|, |T_{i-2}|)$ 的前缀 $D$ 也为 $C$ 的周期，于是这也为 $C$ 的前缀 $T_{i-2}$ 的整周期，设 $T_{i-2}=D^j$，则 $T_{i-1}=D^{j+1},\ T_{i}=D^{2j+1}=D^{j+2}$，所以 $j=1$，这样 $\gcd(|A|, |T_{i-2}|)=|T_{i-2}|$，与假设矛盾，于是 $i={k}$ 时第二部分成立。

当 $i=k$ 时第二部分成立时：

$T_{i+1}=T_{i}T_{i}-B(T_i)=T_iT_i-T_{i-2}=T_iT_{i-1}$，即 $i={k+1}$ 时第一部分成立。

在 $i=1$ 时可能会因为涉及到 $T_{-2}$ 产生一些问题，不过可以利用 $S'$ 没有整周期的性质单独说明。

于是证明完毕。

所以如果 $S'$ 存在整周期可直接计算，否则答案可以拆成 $O(\log n)$ 个 $F_{i}$，其中 $i$ 是 $O(\log n)$ 级别的和，直接暴力计算 $F_{i}$ 里边每个字符的数量即可。