2020 多校第一场

## 2020 Multi-University Training Contest (MUTC) 1, KUT Round [比赛地址（HDU）](http://acm.hdu.edu.cn/search.php?field=problem&key=2020+Multi-University+Training+Contest+1&source=1&searchmode=source) [比赛地址（Vjudge）](https://vjudge.net/problem#OJId=HDU&probNum=&title=&source=2020%20Multi-University%20Training%20Contest%201%20&category=all) 朝鲜场，很难，尽管做好了心理准备还是被暴打（bushi 整场比赛只做了一道题（哭），后来看了题解发现其实还是有一些不错的可做题的。 ### [Distinct Sub-palindromes](http://acm.hdu.edu.cn/showproblem.php?pid=6754) [Vjudge](https://vjudge.net/problem/HDU-6754) 题意：取字符集为英文小写字母。对一个字符串 $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::string` 和 `std::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](http://acm.hdu.edu.cn/showproblem.php?pid=6755) [Vjudge](https://vjudge.net/problem/HDU-6755) 题意：斐波那契数列 $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 算法](https://oi-wiki.org/math/quad-residue/#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](http://acm.hdu.edu.cn/showproblem.php?pid=6756) [Vjudge](https://vjudge.net/problem/HDU-6756) 题意：给定一个简单无向图，每个点有点权。要求实现两种操作：修改一个点的点权，查询某个点的所有邻点的点权的 $\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](http://acm.hdu.edu.cn/showproblem.php?pid=6760) [Vjudge](https://vjudge.net/problem/HDU-6760) 题意：给定整数 $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](http://acm.hdu.edu.cn/showproblem.php?pid=6761) [Vjudge](https://vjudge.net/problem/HDU-6761) 题意：对字符串 $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 分量的末尾字符位置。 ```cpp #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)$。 求解这个的代码如下： ```cpp 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 词以上），希望能从这篇文章中收获一些什么。