UOJ Logo zghtyarecrenj的博客

博客

#202 香山的树 另解

2021-12-11 10:39:24 By zghtyarecrenj

#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)$ 次运算。

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

  1. 逐位确定

    每次算出以 $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 的做法是一样的。

  2. 二分

    每次二分确定一位。时间复杂度:$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)$。

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

  1. $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} $$

  2. $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 Avatar