#202 香山的树另解

这个题大部分人都是用 KMP 自动机+dp 做的。这里是一个不用 KMP 的做法。

记号

字符集为 $\Sigma$，假设最小的字母是 $\mathrm a$，最大的字母是 $\mathrm z$。

$\operatorname{pref}_i$ 表示长度为 $i$ 的前缀，$\operatorname{suf}_i$ 表示长度为 $i$ 的后缀。

一个 Lyndon word 是一个字符串，满足其任意一个非空且不等于自身的后缀小于他自身。

一个 necklace 是一个字符串，他是自己的最小循环表示。

显然，Lyndon word 一定是 necklace，并且一个 necklace 一定可以表示为一个 Lyndon word 的若干次重复。

比如：aab 既是 Lyndon word 又是 necklace，aabaab 不是 Lyndon word 但是是 necklace。

记 $\operatorname{minrot}(a)$ 为 $a$ 的最小表示，$\operatorname{lyn}(a)$ 为 $a$ 的最长 Lyndon 前缀的长度。

记 $\operatorname{largestLyndon}(a)$ 表示不超过 $a$ 的最大 Lyndon word，$\operatorname{largestNecklace}(a)$ 表示不超过 $a$ 的最大 necklace。

简要思路

先实现 $O(n^2)$ 次运算求出一个 Lyndon word $S$ 在长为 $|S|$ 的 Lyndon word 中排名第几（具体方法见下文）。

算法一：求出 $S$ 在长度 $\leq n$ 的 Lyndon word 中的排名

先枚举长度 $l$，然后分类讨论：$l\leq |S|$：$rk(\operatorname{largestLyndon}(\operatorname{pref}(S))$；$l > |S|$：$rk(\operatorname{largestLyndon}(S\mathrm a^{l - |S|}))$。$O(n^3)$ 次运算。

算法二：求出长度 $\leq n$ 的以 $S$ 为前缀的 Lyndon word 个数

先枚举长度 $l$，其贡献为：$rk(\operatorname{largestLyndon}(Sz^{l-|S|}))-rk(\operatorname{largestLyndon}(Sa^{l-|S|}))$。$O(n^3)$ 次运算。

接下来有两种方法解决这个问题：

逐位确定

每次算出以 $p$ 为前缀的 Lyndon word 的个数 $u$，讨论 $k$ 和 $u$ 的关系：

如果 $k > u$，则表示 $p$ 比答案的同样长度的前缀小，$k$ 减去 $u$，$p$ 变大 $1$ 步（这里需要先删去 $p$ 后缀的所有 $\mathrm z$）。如果 $p$ 无法再变大就输出 $-1$。

否则 $p$ 肯定是答案的前缀，在 $p$ 的后面加上 $\mathrm a$。

重复这个过程直到 $p$ 是答案。考虑到整个过程中 $p$ 的字典序递增，所以只会执行 $O(n|\Sigma|)$ 次排名的查询。

因为 $k$ 只有 $10^{15}$，所以我们算排名的时候可以对一个比较大的数取模（我的代码中对 $2^{64}$ 取模），这样不用高精度。

时间复杂度：$O(n^4|\Sigma|)$，和 KMP 的做法是一样的。
二分

每次二分确定一位。时间复杂度：$O(n^4 \log |\Sigma|)$ 次运算，但是容易发现需要高精度。高精度的位数是 $\dfrac {\log |\Sigma|^n} {\log 2^w} = n \log |\Sigma| / w$（压位高精）。总的时间复杂度是 $O(n^6 \log^3 |\Sigma| / w^2)$。在 $n$ 更小，$\Sigma$ 更大的时候，这个方法比较有优势。

接下来说说怎么求出一个 Lyndon word $S$ 在长为 $|S|$ 的 Lyndon word 中排名第几。

$O(n^2)$ ranking

Lemma 1：若 $a$ 是一个 necklace。如果 $x>a_j$，那么 $a_ia_{i+1}\ldots a_{j-1}x$ 比 $a$ 大。

考虑 $a_ia_{i+1}\ldots a_j \geq a_1a_2\ldots a_{j-i+1}$。易证。

算法三：在 $O(n)$ 时间内求出 $\operatorname{minrot}(a)$ 和 $\operatorname{lyn}(a)$，或者判断一个串是不是一个 necklace。

其实是魔改 Duval 算法。初始时 $p=1$，指针 $q=1$。$q$ 在 $a$ 上往后扫，如果 $a_q > a_{q-p}$ 说明存在更长 Lyndon 前缀，更新 $p$；否则说明无法往后扩展，直接退出。如果没有扫完就退出了那么肯定不是 necklace。

Lemma 2：如果 $\operatorname{lyn}(a) = p$，则 $\forall b < \operatorname{suf}_{n-p}$，有 $\operatorname{lyn}(\operatorname{pref}_p b)=p$。

根据算法三易证。

算法四：在 $O(n^2)$ 时间内求出 $\operatorname{largestLyndon}$ 和 $\operatorname{largestNecklace}$。

根据 Lemma 2，如果 $a$ 不是一个 necklace，且 $p=\operatorname{lyn}(a)$，那么大于 $\operatorname{pref}_{p-1}(a_p-1)\mathrm k^{n-p}$ 的串一定不是 necklace。如果一个串是 Lyndon word，那么这个串一定是一个 necklace。

所以我们每次求出 $p$，然后更新 $a$，直到 $a$ 是 necklace 或者 Lyndon word 为止。

注意到在一个 Lyndon word 后面添加若干个 $\mathrm z$ 之后他还是一个 Lyndon word，所以如果在此过程中 $p$ 增大了，那么 $a$ 一定是 necklace 或者 Lyndon word 了。考虑到 $p$ 一定不会不变，所以在没找到答案的时候 $p$ 一定是严格递减的。所以至多更新 $n$ 次 $a$。所以时间复杂度 $O(n^2)$。

令 $a$ 是一个 necklace。记 $B_{t, j} (t \geq j)$ 为长度为 $t$ 并且和 $a$ 有长度至少为 $j$ 的共同前缀并且每个后缀都大于 $a$ 的串的个数。

算法五：在 $O(n^2)$ 时间内求出 $B$。

显然初始状态为 $B_{0,0}=1$，$B_{i,i}=0\ (i\geq1)$。

然后我们对于 $B_{t,j}$ 我们考虑第 $j+1$ 位的选择。根据 Lemma 1，第 $j+1$ 位不能取小于 $a_{j+1}$ 的值。所以我们可以得到转移： $$ B_{t,j} = B_{t, j+1} + (z - a_{j+1}) \cdot B_{t - j - 1,0} $$ 直接 dp，$O(n^2)$。

记 $T(a)$ 表示最小循环表示不大于 $a$ 并且和 $a$ 等长的字符串的数量。

注意到 $T(a) = T(\operatorname{largestNecklace}(a))$，所以我们接下来只考虑 $a$ 为 necklace 的情况。

算法六：在 $O(n^2)$ 时间内求出 $T(a)$。

因为 $T(a) = T(\operatorname{largestNecklace}(a))$，所以我们先把 $a$ 变成 $\operatorname{largestNecklace}(a)$。

我们考虑把所有最小循环小时不大于 $a$ 的字符串 $b$ 分组。

对于任意一个 $b$，我们一定可以找到一个循环移位 $b_ib_{i+1}\ldots b_nb_1b_2\ldots b_{i-1}$ 使得 $b \leq a$。因为可能有多个，所以我们取最小的 $i$。我们把 $b$ 归入 $T_{i, lcp(a, b)}(a)$ 中，其中 $lcp(a,b)$ 表示 $a$ 和 $b$ 的最长公共前缀。

令 $f(i,j)=|T_{i,j}(a)|$。

当 $j=n$ 的时候，$\sum \limits_{i=1}^n f(i,n)$ 显然就是 $a$ 的循环移位的数量。因为 $a$ 已经是一个 necklace 了，所以就是 $\operatorname{lyn}(a)$。

否则我们可以分两种情况讨论。

$i+j \leq n$。这种情况下字符串一定是形如 $c \operatorname{pref}_j de$，其中 $c$ 是长度为 $i-1$ 的每个后缀都大于 $a$ 的字符串，$d$ 是小于 $a_{j+1}$ 的字符，$e$ 是长度为 $n-i-j$ 的任意字符串。所以这种情况下 $$ f(i,j)=B_{i-1,0} \cdot (a_{j+1}-\mathrm a) \cdot |\Sigma|^{n-i-j} $$
$i+j>n$。这种情况下字符串一定是形如 $a_{n-i+2 \ldots j} cd \operatorname{pref}_{n-i+1}$，其中 $c$ 是小于 $a_{j+1}$ 的字符，$d$ 是长为 $n-j-1$ 的字符串。$a_{n-i+2 \ldots j} cd$ 的每个后缀都大于 $a$。

因为 $a$ 是一个 necklace，所以肯定有 $a_{n-i+2\ldots j} \geq \operatorname{pref}_{i+j-n-1}$。

令 $s$ 为最大的满足 $a_{j-s+1\ldots j} = \operatorname{pref}_s$，则 $b_{t\ldots n}>a\ (t \leq i+j-n-1-s)$。

我们可以根据 Lemma 1 在 $O(n^2)$ 时间内预处理出所有的 $s$。

所以直接考虑贡献：$c = a_{s+1}$ 的贡献为 $B_{n-j+s,s+1}$；$c>a_{s+1}$ 的贡献为 $B_{n-j-1,0} \cdot (a_{j+1}-a_{s+1}-1)$。 $$ f(i,j) = B_{n-j+s,s+1} + B_{n-j-1,0} \cdot (a_{j+1}-a_{s+1}-1) $$

因为 $$ T(a) = \sum _{i=1}^n \sum _{j=0}^n f(i,j) $$ 所以我们做一遍简单的求和就可以算出 $T(a)$。

算法七：在 $O(n^2)$ 时间内求出 Lyndon word $a$ 在长度为 $|a|$ 的 Lyndon word 中的排名。

这好像是个广为人知的结论？

$RL(a)$ 表示 $a$ 在同长度的 Lyndon word 中的排名。

令 $P(a)$ 表示最小循环表示不大于 $a$ 并且和 $a$ 等长的不循环字符串的数量。

显然，$RL(a) = P(a)/n$，并且 $T(a) = \sum \limits_{d|n} P(\operatorname{pref}_d)$。

莫比乌斯反演可得 $$ P(a) = \sum _{d|n} \mu \left(\dfrac n d\right) T(\operatorname{pref}_d) $$ 故 $$ RL(a) = \dfrac 1 n \sum _{d|n} \mu \left(\dfrac n d\right) T(\operatorname{pref}_d) $$ Bonus：我们可以用 Burnside 引理得出计算 necklace 排名的方法。

zghtyarecrenj的博客

博客