CTSC 2016 香山的树

题意

给定 \(n, k\) 和 Lyndon 串 \(s_1\)，求长度小于等于 \(n\) 的 Lyndon 串中，按照字典序排在 \(s_1\) 后面 \(k-1\) 名的串 \(s_k\)，或报告无解。\(1\le n\le 50, 1\le k\le 10^{15}\)。

Lyndon 串：字典序严格小于所有自己真后缀的串

题解

只需要计数拥有某个给定前缀 \(p\) 的 Lyndon 串个数即可，假设这一部分我们能做到 \(\Theta(f(|p|, n))\)，那么总复杂度是 \(\Theta\left(|\Sigma|\cdot\sum\limits_{i=1}^{n}f(i, n)\right)\)。

考虑一个 Lyndon 串 \(t\)，有“字典序小于所有真后缀”这个限制，则我们关心所有 \(t\) 的 Z-Box，即它与它的某个后缀的 LCP。每个 Z-Box 都不能顶到字符串末尾，并且它的下一个字符必须比对应的前缀的下一个字符更大。然而 Z-Box 的求法一般不是在线的，和我们希望的 DP 做法不太适合。注意到一个特定起点的 Z-Box 实际上也就是特定前缀的 Border，我们考虑利用 KMP 而非 Z-Box 求解。尽管 KMP 可以在线地进行转移，我们仍然面对一个问题：设某个以 \(p\) 为前缀的串 \(pq\) 有长度为 \(x \ge |p|\) 的 Border，则我们需要知道 \(q_{x-|p|+1}\)，而记录 \(q\) 的每个位置对于 DP 过程而言显然太多了——实际上这样还不如直接枚举所有串。注意使用 KMP 自动机而不是一般的 Border 树。

注意到，当上述情况出现时，一定意味着在 \(pq\) 的后面部分，\(p\) 又出现了一次。而且如果由于上述情况出现了某个后缀的字典序小于等于 \(pq\)，那么这个后缀的开头还是 \(p\)。所以我们首先忽略掉不允许循环移位的限制，然后只考虑长度小于等于 \(|p|\) 的 Border 的合法性，并在计数的同时记录 \(p\) 在整个串中的出现次数 \(j\)，最后再除以 \(j\)，就可以知道所有 Lyndon 串或它的反复的方案数。最后再通过容斥去掉反复形成的串。时间复杂度 \(\Theta(n^2|p|\cdot|\Sigma|)\)。那么总复杂度 \(\Theta(n^4|\Sigma|^2)\)。看起来不太好过。注意到转移的限制是必须通过大于等于最大的非 \(0\) 转移字符的边转移，所以只有向那条边的末端以 \(1\) 的系数转移，或向 \(0\) 以后面的转移个数为系数转移这两种。预处理一下不难做到 \(\Theta(n^4\cdot |\Sigma|)\)。如果采用二分每一位的字符的方法可以做到 \(\Theta(n^4\log |\Sigma|)\)，此外很多部分跑不满。