Sweetlemon 的博客

Sweetlemon 的博客

2020 多校第一场

posted on 2020-07-22 12:47:37 | under 总结 |

2020 Multi-University Training Contest (MUTC) 1, KUT Round

比赛地址(HDU)

比赛地址(Vjudge)

朝鲜场,很难,尽管做好了心理准备还是被暴打(bushi

整场比赛只做了一道题(哭),后来看了题解发现其实还是有一些不错的可做题的。

Distinct Sub-palindromes

Vjudge

题意:取字符集为英文小写字母。对一个字符串 $S$,令 $f(S)$ 表示它的本质不同回文子串的个数。令 $g(n)$ 表示长度为 $n$ 的字符串中 $f(S)$ 的最小值,求长度为 $n$ 的字符串中 $f(S)=g(n)$(即取到最小值)的字符串个数。

这题一看好吓人,但这题的 AC 数量是最多的,因此就开始强攻。

在来机房的路上口算推出了 $g(4)=g(5)=3$,并且取到最小值的字符串都是 $\mathtt{abca},\mathtt{abcab}$ 这样的;来到机房,又在纸上推出了 $g(1)=1,g(2)=2,g(3)=3$;并且任意长度不大于 $3$ 的字符串都恰取到最小值。

可是 $g(6)$ 难以手推,于是开始写暴力,用 std::stringstd::unordered_set 辅助统计本质不同的回文子串,结果惊奇地发现 $g(6),g(7),g(8)$ 都等于 $3$ 啊!把取到最小值的字符串打印出来,也长成 $\mathtt{abcabcab}$ 这种样子。

于是开始粗略证明。对于长度不小于 $4$ 的字符串, $f(S)$ 肯定不会是 $1$ 或 $2$(简单考虑只有一种或两种字符的长度为 $3$ 的字符串即得证)。因此我们只需要构造一种 $f(S)=3$ 的方案就好了。 $\mathtt{abcabcab}$ 这样的字符串,肯定没有非平凡(长度超过 $1$)的回文子串,因此 $f(S)=3$。再证明 $f(S)=3$ 的字符串都长这样。首先这样的字符串中肯定有三种字符,为了让 $f(S)=3$,字符串中一定不能出现非平凡回文子串,简单讨论一下就得到了 $\mathtt{abcabcab}$ 这样的结构。

因此这题只有四种答案, $n\le 3$ 时是 $26^n$, $n\ge 4$ 时是 $\mathrm{A}_{26}^3$。果然是一道假题,不过这签到题也太难了吧。

Fibonacci Sum

Vjudge

题意:斐波那契数列 $F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2}\ (n\ge 2)$。给定 $n,c,k$,求 $\sum_{i=1}^{n}F_{ic}^k$。 $1\le n,c\le 10^{18},\ 1\le k\le 10^5$。

如果 $k=1$,也许是可以用矩阵快速幂做的:先处理出 $c$ 项的转移矩阵,再乘就可以了。

但现在有个 $k$,怎么办呢?

我们再推一下吧,推个 $k=2$,勉强有一点规律,但是 $k=2,c\neq 1$ 就做不了了。 $k=3$ 更是连推都推不下去了。

因此,由于矩阵难以处理“乘”,我们可能要考虑其他方法。

什么东西可以乘方,还可以方便地处理周期呢?通项公式啊!我们知道 $F_n=\cfrac{1}{\sqrt{5}}\left(\alpha^n-\beta^n\right)$,其中 $\alpha=\cfrac{1+\sqrt{5}}{2},\beta=\cfrac{1-\sqrt{5}}{2}$。等等, $\alpha,\beta$ 都是无理数,外面还带了 $\sqrt{5}$,这怎么取模啊?

好消息是,有个叫二次剩余的东西:如果存在模意义下整数 $\gamma$,使得 $\gamma^2 \equiv 5$,那么就可以把 $\gamma$ 当作模意义下的 $\sqrt{5}$ 了!

为什么呢?感性理解一下,最后的答案是个整数,因此肯定只会出现 $\sqrt{5}$ 的偶数次方;做偶数次方时 $\gamma$ 和 $\sqrt{5}$ 的表现相同,因此就可以用 $\gamma$ 代替 $\sqrt{5}$ 了。

$\gamma$ 是否存在呢?也就是说,如果 $5$ 是二次非剩余不就完蛋了?正因为如此,这题使用的模数是不那么常见的 $10^9+9$,在这个模数下 $5$ 是二次剩余。

$\gamma$ 等于多少呢?如果不会 Cipolla 算法,我们可以本地枚举,得到 $\gamma=383008016$。因此我们知道, $\cfrac{1}{\sqrt{5}}\equiv \gamma^{-1}$, $\alpha\equiv \cfrac{1+\gamma}{2},\beta\equiv \cfrac{1-\gamma}{2}$。

接下来就好办了。 $F_n=\cfrac{1}{\gamma}\left(\alpha^n-\beta^n\right)$,那么 $F_n^k=\left(\cfrac{1}{\gamma}\right)^k(\alpha^n-\beta^n)^k$,用二项式定理展开,得到 $F_{n}^{k}=\left(\cfrac{1}{\gamma}\right)^k\sum_{i=0}^{k}\mathrm{C}_k^i(-1)^k\alpha^{(k-i)n}\beta^{in}$。

这个式子对 $n=jc\ (j=1,2,\cdots,n)$ 求和得到:

$$\sum_{j=1}^{n}F_{jc}^{k}=\left(\cfrac{1}{\gamma}\right)^k\sum_{i=0}^{k}\mathrm{C}_k^i(-1)^k\left(\sum_{j=1}^{n}\alpha^{(k-i)cj}\beta^{icj}\right)$$

最后一个括号里是一个首项和公比都为 $\alpha^{(k-i)c}\beta^{ic}$ 的等比数列求和,于是就可以做了。

唯有一点是需要注意的,等比数列求和怎么求?

废话,肯定是 $S=\cfrac{a_{n+1}-a_1}{q-1}$ 啦,都用到吐了。

那你就完啦!这个公式仅在 $q\neq 1$ 的时候适用, $q=1$ 的时候要特别讨论,此时 $S=na_1$。

这个东西是高考的易错点,也是这里的易错点,因为对 $0$ 求逆不会报错,只会返回 $0$,这样错误就难以发现;因此可以包装一个求逆元函数,在里面对待求逆的数进行断言(当然会稍减慢速度)。

Finding a MEX

Vjudge

题意:给定一个简单无向图,每个点有点权。要求实现两种操作:修改一个点的点权,查询某个点的所有邻点的点权的 $\mathrm{mex}$(没有出现的最小自然数)。点数 $n$,边数 $m$,操作数 $q$ 满足 $1\le n,m,q\le 10^5$,点权为 $[0,10^9]$ 中的整数,时限 $3\mathrm{\ s}$。

数据结构题,题意简明。“邻点”让我们想到了度数分治:总度数是 $2m$,因此度数不小于 $\sqrt{2m}$ 的点不多于 $\sqrt{2m}$ 个,称为“重点”;其余点为“轻点”。重点由邻点来找,自己只维护自己的信息;轻点主动去找邻点更新自己的信息。

怎么找 $\mathrm{mex}$ 呢?可以每个点开一棵平衡树(大雾),或者用树状数组、线段树之类。如果用平衡树,整张图只存了 $2m$ 个数,空间复杂度正确;如果用树状数组一类,空间复杂度似乎不太对?

当然,这样做无论是修改还是查询都是 $\mathrm{O}(\log n)$ 级别的,而查询只有 $\mathrm{O}(q)$,修改却有 $\mathrm{O}(\sqrt{n}q)$ 次,二者发展不平衡,可以考虑移动分块平衡。将值域分块,每块维护“出现的数的种类数”,这样就可以 $\mathrm{O}(1)$ 修改, $\mathrm{O}(\sqrt{n})$ 查询了。可是这样空间复杂度好像又不太对,每块维护的信息 $\mathrm{O}(n\sqrt{n})$ 可以存完,但每个位置的桶肯定是开不下的。于是改成 std::unordered_map,强行满足要求。

为了让块的个数变成 $\mathrm{O}(\sqrt{n})$,我们需要把值域缩小到 $n$ 级别。如果离散化,就不便处理 $\mathrm{mex}$,这怎么办呢?我们发现,一个点的 $\mathrm{mex}$ 不会超过 $n$,因此可以把大于 $n$ 的点权都变成 $n$。

好不容易写完,交上去 TLE 了。唉,只能怪 unordered_map 常数实在太大,因此使用时需谨慎。

怎么办呢?我们其实可以考虑得更精细一些。点 $u$ 的 $\mathrm{mex}$ 最大是多少呢?刚才我们给出的回答是 $n$,这就太笼统了;事实上,这个上界可以改成 $\deg(u)$。因此,我们在处理信息时,要把点权与目标点的度数取 $\min$,这样就可以开下每个位置的桶了——总共只需要 $2m+n$ 个桶嘛(别忘了 $0$ 也要桶)!

然而这题多组数据,如果用 vector 开桶,要小心被卡到 MLE,于是可以用一种“一维数组模拟二维数组”的技术。

事实上,题解用的是 $\mathrm{O}(n\sqrt{n}\log n)$ 的写法,不过树状数组常数小,多一个 $\log$ 可能差距不大。

Math is Simple

Vjudge

题意:给定整数 $n$,计算下式。

$$\sum_{1\le a<b\le n} [a\perp b] [a+b\ge n] \cfrac{1}{ab}$$

这个题目的求和限制比较奇怪,一共三个条件,其中的两个是我们熟悉的,另外一个 $a+b\ge n$ 是我们不熟悉的。如果直接将 $a\perp b$ 通过枚举因数和求 $\mu$ 转化,就会做不下去。

如果不能直接做,我们试试能不能递推。设 $f_n=\sum_{1\le a<b\le n}[a\perp b][a+b\ge n]\cfrac{1}{ab}\ (n\ge 2)$,那么是否能在 $f_n$ 和 $f_{n-1}$ 之间建立递推呢?

经过仔细观察与 $n$ 有关的 $1\le a<b\le n$ 和 $a+b\ge n$ 两个条件,我们发现,从 $f_{n-1}$ 到 $f_n$,增加的 $(a,b)$ 对是 $1\le a<b=n$ 的,减少的 $(a,b)$ 对是 $a+b=n-1$ 的。

增加的 $(a,b)$ 对的权值和是 $\sum_{1\le a<n}[a\perp n]\cfrac{1}{na}$(在上式中令 $b=n$ 得到)。

减少的 $(a,b)$ 对的权值和为 $\sum_{1\le a<n-1}[a\perp (n-1-a)][a<(n-1-a)]\cfrac{a+b}{(n-1)ab}=\cfrac{1}{n-1}\sum_{1\le a<n-1}[a\perp (n-1)][a<(n-1-a)]\left(\cfrac{1}{a}+\cfrac{1}{n-1-a}\right)$,这里用了裂项技巧, $\cfrac{1}{ab}=\cfrac{1}{a+b}\left(\cfrac{1}{a}+\cfrac{1}{b}\right)$。考虑与 $n-1$ 互质且和为 $n-1$ 的互异正整数对。如果 $n-1\le 2$,那么这样的整数对不存在;如果 $n-1\ge 3$,那么这样的整数对中,每个与 $n-1$ 互质的整数恰好出现一次。因此,这个式子在 $n-1\le 2$ 时值为 $0$, $n-1\ge 3$ 时值为 $\cfrac{1}{n-1}\sum_{1\le a<n-1}[a\perp (n-1)]\cfrac{1}{a}=\sum_{1\le a<n-1}[a\perp (n-1)]\cfrac{1}{(n-1)a}$——这与“增加的权值”形式相似,我们记它为 $g_n=\sum_{1\le i<n}[i\perp n]\cfrac{1}{ni}$。

因此, $f_n=\begin{aligned}\begin{cases}&f_{n-1}+g_n-g_{n-1},&n\ge 4\\ &f_{n-1}+g_n,&n=3\end{cases}\end{aligned}$。

这里 $f_2=\cfrac{1}{2}$。

上面这个递推式可以经过迭代求和化简,得到 $f_2=\cfrac{1}{2},f_n=f_2+g_n=\cfrac{1}{2}+g_n\ (n\ge 3)$。这是关键的一步,条件顿时少了很多。

那么现在问题变为计算 $g_n=\sum_{1\le i<n}[i\perp n]\cfrac{1}{ni}=\cfrac{1}{n}\sum_{1\le i\le n}[i\perp n]\cfrac{1}{i}$。这是我们熟悉的,可以化简得到 $g_n=\cfrac{1}{n}\sum_{d\mid n}\cfrac{\mu(d)}{d}H\left(\cfrac{n}{d}\right)$,其中 $H$ 是调和级数, $H(n)=1+\cfrac{1}{2}+\cfrac{1}{3}+\cdots+\cfrac{1}{n}$,可以 $\mathrm{O}(n)$ 预处理。因此这个式子就可以枚举因数做到 $\mathrm{O}(\sqrt{n})$ 计算。

另外注意,由于 $n$ 很大,只能开一个 $n$ 大小的数组;可以用质因数分解的方法枚举因数并获得 $\mu$,当然要注意,分解质因数之前要把原来的数备份一份。

回顾整个过程,重要的是建立递推式和发现“增加的权值”和“减少的权值”之间的共同点并化简设出 $g_n$,还是非常有难度和价值的一道题目。

Minimum Index

Vjudge

题意:对字符串 $S$ 的所有 $n$ 个前缀 $S_1,S_2,\cdots,S_n$,分别求出 $\mathrm{sa}[1]$(字典序最小的后缀的编号),并加权输出。所有测试数据组的 $n$ 之和不大于 $2\times 10^7$。

这么大的数据范围,什么后缀数组、后缀树、后缀自动机都没有办法解了,哈希 + 二分也没有办法。

这里我们有一个新算法,可以在 $\mathrm{O}(n)$ 复杂度内解决类似问题,这就是著名的 Lyndon 分解。

初次听到这个是在 WC 2019 的第一课堂,当时完全没有听懂;就是到现在也没有完全弄懂,不过可以勉强弄出来。

首先,是 Lyndon 串的定义:一个串是 Lyndon 串当且仅当这个串的 $\mathrm{sa}[1]=1$,即最小的后缀是它自身。事实上,这等价于它比它的其他循环同构串都要小,但我不完全会证明这一点。为了叙述方便,下面令所有 Lyndon 串的集合为 $\mathscr{L}$(这个字母好飘逸)。

接着是 Lyndon 串的几个性质,这里不做严格证明,因为我实在是不会证

第一个是关于 Lyndon 串的拼合的。如果 $u,v\in \mathscr{L}$ 且 $u<v$,那么 $uv$(两个串的拼合)也属于 $\mathscr{L}$。这个应该很容易理解,其他后缀基本上要么比 $v$ 大,要么直接比 $u$ 大。

第二个是关于 Lyndon 串的判定的。如果 $r\mathrm{c}$ 是一个 Lyndon 串的前缀,其中 $r$ 是字符串而 $\mathrm{c}$ 是字符,而 $\mathrm{d}$ 是一个比 $\mathrm{c}$ 大的字符,那么 $r\mathrm{d}\in \mathscr{L}$。

这个怎么理解呢?设 $r\mathrm{c}t$ 是我们所说的 Lyndon 串,且 $r’$ 是 $r$ 的一个真后缀(可以为空),那么根据 Lyndon 串的性质, $r'\mathrm{c}t>r\mathrm{c}t$(否则 $r'\mathrm{c}t$ 就是一个更小的后缀,矛盾),并且根据真后缀的长度性质, $\vert r'\mathrm{c}\vert\le \vert r\vert$。 $r'\mathrm{c}$ 和 $r$ 的字典序关系如何呢?假设 $r'\mathrm{c}<r$,那么 $r'\mathrm{c}t$ 在与 $r\mathrm{c}t$ 进行字典序比较的时候,还没比到 $r\mathrm{c} t$ 的 $\mathrm{c}$, $r\mathrm{c}t$ 就“出师未捷身先死”了,所以这是不可能的。据此, $r'\mathrm{c}\ge r$。

由于 $\mathrm{d}>\mathrm{c}$,因此 $r'\mathrm{d}>r'\mathrm{c}\ge r$,因此 $r'\mathrm{d}>r\mathrm{d}$(胜方在胜利后无论怎么浪都已经赢了,所以不管在 $r$ 后面加什么,它都比 $r'\mathrm{d}$ 小)。由于 $r'\mathrm{d}$ 穷尽了 $r\mathrm{d}$ 的所有真后缀,它们都比 $r\mathrm{d}$ 小,因此 $r\mathrm{d}\in \mathscr{L}$。

这两个性质理解完毕,我们来看 Lyndon 分解。

Lyndon 分解就是把字符串分解成若干个“不可再合并”的 Lyndon 串。什么叫“不可再合并”呢?回忆 Lyndon 串的第一个性质,如果 $u,v\in \mathscr{L}$ 且 $u<v$,那么 $uv \in \mathscr{L}$。也就是说,为了“不可再合并”,字符串 $s$ 分解出来的 Lyndon 串 $s_1,s_2,\cdots,s_m$ 一定要满足 $\forall 1\le i<m,s_i\ge s_{i+1}$。这样,我们就可以导出 $s_1\ge s_2\ge \cdots \ge s_m$。

我们想要做这个分解,首先它得存在吧?存在性比较容易证明:长度为 $1$ 的串一定是 Lyndon 串,因此首先我们把字符串 $s$ 分解成单个字母,接着不断遍历寻找有没有满足 $s_i<s_{i+1}$ 的两个相邻 Lyndon 串,如果有就合并,没有就完成了 Lyndon 分解。当然这个分解算法的效率很低。

事实上,Lyndon 分解还是唯一的。假设 $s$ 有两个 Lyndon 分解 $s_1s_2s_3\cdots s_is_{i+1}\cdots$ 和 $s_1s_2s_3\cdots s'_is'_{i+1}\cdots$,这两个分解从 $s_i$ 和 $s'_i$ 开始不同。不妨设 $s_i$ 更长一点,那么 $s_i$ 包含了第二个分解中几个 Lyndon 串的内容。设 $s_i=s'_is'_{i+1}\cdots s'_js'_{j+1}[:u]$,即它包含了 $s'_i$ 到 $s'_j$ 这些 Lyndon 串的全部字符和 $s'_{j+1}$ 的前 $u$ 个字符。那么 $s'_{j+1}[:u]$ 是 $s_i$ 的一个真后缀,根据 Lyndon 串的性质, $s_i<s'_{j+1}[:u]$。

根据字典序的性质, $s'_{j+1}[:u]\le s'_{j+1}$(空字符更小)。根据 Lyndon 分解的性质, $s'_i\ge s'_{i+1}\ge\cdots\ge s'_{j+1}$,从而通过一系列不等式我们得到 $s_i<s'_i$。但是 $s'_i$ 是 $s_i$ 的真前缀啊,真前缀的字典序怎么可能比整个字符串大呢?这就矛盾了,因此 Lyndon 分解是唯一的。

这样一个存在且唯一的 Lyndon 分解,我们怎么求它呢?

首先来个暴力算法。先证明一个性质:一个字符串 $s$ 的最小后缀 $w$ 就是它 Lyndon 分解的最后一个 Lyndon 串 $s_m$。首先, $w$ 肯定不能从 Lyndon 分解中某个 Lyndon 串的中间开始,要不然那个 Lyndon 串的字典序比 $w$ 的一个前缀要小, $w$ 就不是最小后缀了。因此, $w$ 一定是最后的若干个 Lyndon 串的拼合。但是 Lyndon 分解要求“不可以再合并”,因此 $w$ 不可能是多个 Lyndon 串的拼合,于是 $w=s_m$。

有了这个性质,我们只要每次找出 $s$ 的最小后缀,再接着分解前面的部分就可以了。这还真是暴力啊。

现在说一个神奇的 $\mathrm{O}(n)$ 算法——Duval 算法。

再来证明一个性质,Lyndon 分解是可以随便分的——把字符串 $s$ 划分为一些非空子串 $p_1,p_2,\cdots,p_u$,并把这些非空子串分别做 Lyndon 分解,把分解结果按顺序连接,把该合并的合并,最后肯定能得到 $s$ 的 Lyndon 分解。这个可以由 Lyndon 分解的存在性和唯一性得到。如果我们划分得比较准确,使得这些非空子串的 Lyndon 分解连接起来之后不能再合并,那就完成了 Lyndon 分解。

从这个性质我们又能得到一个推论——如果 $s$ 有一个 Lyndon 子串 $s_0$(可能是本身),那么它一定完整地出现在 $s$ 的 Lyndon 分解的某个分量中,而不可能被切分。

为什么呢?先证一个简单的版本:Lyndon 串的 Lyndon 分解就是本身。这是比较“显然”的,因为它本身是一个 Lyndon 分解,由 Lyndon 分解的唯一性证毕。

再考虑 $s_0\neq s$ 的情形。这时把 $s$ 分成三部分—— $s_0$ 之前、 $s_0$、 $s_0$ 之后,分别 Lyndon 分解,再连接起来。由上一段的讨论我们知道, $s_0$ 的 Lyndon 分解就是它本身;那么说明合并开始时有“ $s_0$”这一个 Lyndon 串。在合并的过程中,这个 $s_0$ 只会被不断合并而不会被切开,因此到最后它一定完整地出现在某个 Lyndon 分量中。推论证毕。

在这个算法的运行过程中,我们把字符串 $s$ 分为三个部分: $i$ 号字符以前的部分为分解完成区,这里的字符串已经完成 Lyndon 分解,后面部分分解后与这里的 Lyndon 串连接起来,一定不会发生合并; $i$ 号字符到 $k$ 号字符正在进行 Lyndon 分解,其中 $k$ 是正在加入的字符; $k$ 号字符以后还未处理。 $i$ 号字符到 $k$ 号字符的区域由一个 Lyndon 串 $t$ 的若干次重复与 $t$ 的一个可以为空的真前缀 $p$ 组成,即这部分为 $tt\cdots tp$,我们计划把这些 $t$ 作为 Lyndon 分量加入到 Lyndon 分解中。设 $l=\vert t\vert$,用一个指针 $j$ 维护 $k-l$ 这个位置,也就是 $k$ 对应的上一个周期的位置。

算法运行过程中, $k$ 指针每到一个新的位置,就讨论 $s[k]$ 和 $s[j]$ 的大小关系。

  • 若 $s[j]=s[k]$,周期关系(循环不变式)可以维持,继续同步右移 $j,k$ 指针。

  • 若 $s[j]<s[k]$,那么注意到 $p$ 是 Lyndon 串 $t$ 的前缀,拼上 $s[k]$(一个比 $p$ 在 $t$ 中的下一个字符大的字符)一定会得到一个 Lyndon 串 $t’$ ,并且还满足 $t'>t$。于是此时正在分解区可以表示为 $tt\cdots tt'$,其中 $t,t'\in \mathscr{L}$,且 $t<t'$。根据 Lyndon 串的合并方法, $tt'$ 也是 Lyndon 串; $tt'>t$,于是 $ttt'$ 也是 Lyndon 串;不断合并,最终知道 $tt\cdots tt'$ 整个是一个 Lyndon 串。

    考虑上面的推论。由于 $tt\cdots tt'$ 是 Lyndon 串,因此在最终的分解中它不可能被切分。于是我们应该调整我们计划加入到 Lyndon 分解中的分量(原计划把 $t$ 作为 Lyndon 分量加入,现在知道这是不可能的),把 $tt\cdots tt'$ 整体作为新的 $t$。因此应该在 $k$ 自增的同时令 $j=i$,这样 $k,j$ 同时指向一个周期的开始。

  • 若 $s[j]>s[k]$,那么这实际上告诉我们,我们计划加入的 $t$ 符合实际,也就是这些 $t$ 可以加入到最终的 Lyndon 分解中。

    为什么呢?考虑把 $s$ 切成最多三部分, $tt\cdots t$ 之前、 $tt\cdots t$ 和 $tt\cdots t$ 之后,那么 $tt\cdots t$ 这一段的 Lyndon 分解一定是 $t,t,\cdots, t$ 这些分量。下面证明 $t$ 既不能和前面合并,又不能和后面合并。

    $t$ 不能和前面合并其实是算法循环不变式的保证(“后面部分分解后与这里的 Lyndon 串连接起来,一定不会发生合并”),那么只需要证明 $t$ 不能和后面合并,这样就能保证循环不变式继续成立了。

    考虑后面部分进行 Lyndon 分解得到的第一个分量 $u$。如果 $u$ 包含字符 $s[k]$,那么由于 $s[k]<s[j]$,知 $u<t$,不能合并;如果 $u$ 不包含字符 $s[k]$,那么 $u$ 是 $t$ 的前缀,同样有 $u<t$,也不能合并。证毕。

    由于这些 $t$ 不能和前后合并,那么它们一定出现在最终的 Lyndon 分解中,我们可以从此划分 $s$,再从 $p$ 的开头位置重新开始 Lyndon 分解。

另外,如果 $k$ 到了 $n+1$ 的位置,视同 $s[j]>s[k]$(可以理解为空字符最小)。

整个算法中,只有 $s[j]>s[k]$ 一种情况确定了 Lyndon 分量,其他情况都是在调整当前的“划分计划”。

空谈过于抽象,我们看一下代码。下面这段代码能够输出一个字符串所有 Lyndon 分量的末尾字符位置。

#include <cstdio>
#include <cstring>
#define MAXN 1000005
using namespace std;

char tstr[MAXN];

int main(void){
    scanf("%s",tstr+1);
    int ren=strlen(tstr+1); //长度
    int pti=1; //待分解区开始点,即 i 指针
    while (pti<=ren){
        int ptj=pti,ptk=ptj+1; //读入点的对应点, 读入点,分别是 j, k 指针
        while (ptk<=ren){
            if (tstr[ptj]==tstr[ptk]){
                ptj++,ptk++; //延续周期,第一种情况
                continue;
            }
            if (tstr[ptj]>tstr[ptk])
                break; //将未满周期前缀 p 独立出来,第三种情况
            //tstr[ptj]<tstr[ptk],第二种情况
            ptj=pti,ptk++; //tt...tt' 合并为新的 t
        }
        int tdis=ptk-ptj; //周期长度
        while (pti<=ptj)
            pti+=tdis, ayano(pti-1); //不断跳到下一个周期串开始点,输出当前 Lyndon 分量的末尾字符位置
    }
    return 0;
}

这不是最为简洁的实现,但比较容易理解。代码中 while (pti<=ren) 的大循环中,每一次就将一批 $tt\cdots t$ 加入到 Lyndon 分量中,可以看出,这个算法划分 $s$ 的标准是“按 Lyndon 分量大小递减分为几个相等的块”,比如用数字表示 Lyndon 分量的相对大小,且这个字符串的 Lyndon 分解表示为 $4,4,3,2,2,2,1$,那么 $(4,4); (3);(2,2,2);(1)$ 分别会在一次大循环中加入。

在这个算法的过程中,我们可以解决这一道题目,也就是可以动态得出 $s$ 的前缀的 $\mathrm{sa}[1]$,或者说最后一个 Lyndon 分量的位置。根据 Lyndon 分解可拆的性质,最后一个 Lyndon 分量一定在“正在分解”区而不在“分解完毕”区(可以把前缀串拆成“正在分解”区的部分和“分解完毕”区的部分讨论)。那么对于当前前缀,最后一个 Lyndon 分量的开头在哪里呢?

如果当前前缀是 $t$ 串的结尾,也就是 $s[j]<s[k]$ 这类情况,那么最后一个 Lyndon 分量的开头就在 $i$ 处;如果 $s[j]>s[k]$,那么说明这里还要再重新分解,暂不回答这里的问题,稍后再处理。

那么现在的问题就是 $s[j]=s[k]$ 的时候了。如果 $s[j]=s[k]$,那么就意味着这里是上一个周期的重复。记当前的“正在分解”区的字符串为 $ss\cdots sp$,那么把它拆成 $ss\cdots s$ 和 $p$ 分别进行 Lyndon 分解,得到了 $s,s,\cdots,s$ 和 $p$ 的一个分解。由于 $p$ 是 $s$ 的前缀,知 $p<s$,于是 $s,p$ 的分解不能合并;因此 $s[k]$ 这里的最后一个 Lyndon 分量就是 $p$ 相应位置的最后一个 Lyndon 分量。考虑上一个周期( $s[j]$),那里也是 $ss\cdots sp$ 的样子,只不过少了一个 $s$ 而已。因此, $s[k]$ 处的最后一个 Lyndon 分量与 $s[j]$ 处的最后一个 Lyndon 分量的内容相同,但是位置相隔一个周期。因此 $\mathrm{ans}[k]=\mathrm{ans}[j]+(k-j)$。

求解这个的代码如下:

scanf("%s",tstr+1);
int ren=strlen(tstr+1);
int pti=1; //待分解区开始点
while (pti<=ren){
    int ptj=pti,ptk=ptj+1; //读入点的对应点, 读入点
    anss[pti]=pti; //pti 的位置是 Lyndon 串的开头和结尾
    while (ptk<=ren){
        if (tstr[ptj]==tstr[ptk]){
            anss[ptk]=anss[ptj]+(ptk-ptj); //按周期继承 ptj 的答案
            ptj++,ptk++; //延续周期
            continue;
        }
        if (tstr[ptj]>tstr[ptk])
            break; //将未满周期前缀独立出来,答案下次再讨论
        //tstr[ptj]<tstr[ptk];
        anss[ptk]=pti,ptj=pti,ptk++; //Lyndon 合并,此时 ptk 是 Lyndon 串的末尾,答案应为这个 Lyndon 串的开头 pti
    }
    int tdis=ptk-ptj; //周期长度
    while (pti<=ptj)
        pti+=tdis; //不断跳到下一个周期串开始点

前面我们说这个算法的复杂度是 $\mathrm{O}(n)$ 的,那么怎么证明呢?

其实证明很简单。我们看 $k$ 指针,它几乎是单调右移的,但有时候它会往回跳,就是 $s[k]>s[j]$ 的时候。 $k$ 会回跳至多一个周期的长度,但我们注意到,此时 $i$ 也会右移至少一个周期的长度。因此 $k$ 回跳的长度不大于 $i$ 右移的长度,于是 $k$ 最多回跳 $n$ 个长度,由此知这个算法是 $\mathrm{O}(n)$ 的。

到这里,我们就完整解决了这道题,同时还学习了一个代码很短的 $\mathrm{O}(n)$ 字符串算法。总的来说,这道题比较接近于 Lyndon 分解模板题,但要求对算法有一定的理解。

那么这篇总结到此就告一段落了,这也许是我写过的最长的一篇比赛总结了吧(Typora 统计 7300 词以上),希望能从这篇文章中收获一些什么。