QOJ 7008 另解

文中符号：

• \(\operatorname{Period}(s)\)：字符串 \(s\) 的周期集合。
• \(\operatorname{Per}(s)\)：字符串 \(s\) 的最小周期。
• 循环节：\(x\in \operatorname{Period}(s)\) 且 \(x| \operatorname{len}(S)\)。
• \(\operatorname{Cyc}(s)\)：\(s\) 的最小循环节。
• \(\operatorname{endpos}(x)\)：后缀自动机上结点 \(x\) 的 \(\operatorname{endpos}\) 集合中任意一个元素。

若有 \(TP=PT\)，则 \(P\) 必定为 \(\operatorname{Cyc}(s)^k\)。

考虑先计算出所有本质不同的子串个数，再减去不合法的方案数。（这里计数 \(TP\)，而不是 \(T\)）。

所以我们要求所有本质不同的 \(a^k\) 个数，其中 \(k\ge 2\)。

考虑优秀的拆分的做法，我们可以在 \(\mathcal{O}(n\log n)\) 求出所有 \((l, r, k)\)，满足：

• \(k\in \operatorname{Period}(s[l, r])\)
• 不存在 \(l',r'\)，满足 \(l'\le l\le r\le r'\) 且 \(k\in \operatorname{Period}(s[l', r'])\)。（换句话说，这个 \((l, r)\) 是级长的）。

但是这样很难和本质不同子串扯出联系。

SAM 是对付本质不同的利器，SAM 中的一个结点 \(u\) 对应着 \(l\in [\operatorname{endpos}(u)-\operatorname{len}((u)+1,\operatorname{endpos}(u)-\operatorname{len}(\operatorname{link}(u))], r=\operatorname{endpos}(u)\) 这些子串。

猜想 I：每个节点中所代表的所有字串上，若 \(\operatorname{Cyc}\) 存在，则 \(\operatorname{Cyc}\) 唯一。

结论：猜想 I 是错误的。反例：\(s=\texttt{baababaabab}\)。存在一个节点 \(u\) 包含 \({\texttt{abaaba,babaaba,ababaaba,aababaaba,baababaaba}}\)，周期为 \(3, 5\)。

猜想 II：每个节点中所代表的所有字串上，至多有两个不同的 \(\operatorname{Cyc}\)，若存在两个，则一个为最大，一个为最小。（这个最大和最小可能不是很清楚，可以查看下面的步骤）。

结论：我们暂时不知道猜想 II 是否正确。（本机对拍没有找到反例）若猜想 II 被证伪，还有比较弱的猜想 III（同样，未被证明！）。

猜想 III：每个节点中所代表的所有字串上，至多有 \(\log n\) 个不同的 \(\operatorname{Cyc}\)。

不过先别急。在处理出所有三元组 \((l, r, k)\) 后，将所有 \(i\in [l + 2k - 1, r]\) 打上标记 \((l, k)\)，表示 \(k\in \operatorname{Period}(s[l,i])\)。

将 SAM 的节点 \(u\) 挂到 \(\operatorname{endpos}(u)\) 下处理，扫描线维护所有标记。

当扫到 \(\operatorname{endpos}(u)=i\) 的时候做以下操作：

• 取出最小的 \(k\) 满足 \((l, k)\) 中的 \(l\le i-\operatorname{len}(\operatorname{link}(u))\)

• 计算 \(L\in [\max(l,i-\operatorname{len}(u)+1)],R=i\) 的字串有多少长度是 \(k\) 的倍数。

• 取出最大的 \(K\) 满足 \((L, K)\) 中的 \(l\le i-\operatorname{len}(\operatorname{link}(u))\)。

• 若 \(K\) 不为 \(k\) 的倍数，像第二步一样统计 \(K\) 的贡献。

实现。