CTSC2016 香山的树
题意
给定字符串 (S)，求字典序大于等于 (S) ，长度小于等于 (n) 的 Lyndon 串中第 (k) 小的串。
(|S| le 50, |Sigma| = 26, k le 10^{15})。
题解
计数 Lyndon 串
定义一个串 (s) 是循环串当且仅当存在 (t^n = sspace (n > 1)) 。
如果没有字典序的限制，可以注意到如果一个串 (s) 不是循环串，那么这个串的最小起点是唯一的。
不存在非平凡整周期的串数可以通过将 (f(n) = |Sigma|^n) 和 (mu) 做 Dirichlet 卷积得到。
用 Trie 树限制字典序
对于字典序的限制，考虑类似于线段树上二分的过程，我们在 Trie 上递归解决问题（实现时注意一个非叶子的 Lyndon 串节点对答案可以产生贡献）
问题转化成求 Trie 上一个子树的大小，即以某个串为前缀，长度不超过 (n) 的 Lyndon 串数。
计数以 (p) 为前缀的 Lyndon 串数
设当前考虑的前缀为 (p)。对于一个符合要求的串 (s)，其 所有子串 满足 (s < p) 或 (s) 是 (p) 的前缀。
这个限制可以通过对 (p) 预处理 KMP 自动机处理。如果一个节点的一条出边（的字符）小于这个节点的另一条不指向根节点的出边（即可以匹配 (s)）的字符，则这条出边需要删除。
仍然假设 (oldsymbol{s}) 不是循环串，则将 (s) 无限重复后，选择的最小起始位置是唯一的，且是所有 (p) 出现的 起始位置 中的一个。
设 (F(L, node, cnt)) 表示长度为 (L)，在 KMP 自动机上匹配的节点为 (node)，且已经匹配 (s) 次数 (cnt)。那么一个次数 (cnt) 的方案对答案的贡献为 (1 / cnt)。最后需要在串尾加上 (s) （除最后一个字符外）来解决匹配 (p) 的末尾超过 (s) 的情形。 转移枚举下一个字符即可。
考虑去除循环串的方案。记 (ans_i) 表示长度为 (i) ，且无限重复后以 (p) 为前缀的串数。对于 (i le |p|)，(ans_i = 1) 当且仅当 (i) 前缀是 Lyndon 串且 (i) 为 (p) 的周期，否则为 (0)。
对于 (i > |p|)，可以先用 DP 数组的值求出不考虑循环串的答案。注意到对于 (t^c = s)，(t) 对于 (ans_{|s|}) 的贡献为 (1 / c)（注意到本质相同的起点只被计入一次贡献，且这个系数对于 (|t| le |p|) 和 (|t| > p) 都成立），那么按照这个系数去除循环串贡献即可。
注意到 KMP 自动机上每个点可以转移到的节点只有 (2) 种，那么可以 (mathcal O(1)) 转移，DP 一次的复杂度为 (mathcal O(|p|^3))，共访问 (mathcal O(n|Sigma|)) 个 Trie 树节点，那么复杂度 (mathcal O(n^4 |Sigma|))。
状态存储可以直接使用 long double，(64) bit 有效精度可以满足 (10^{15}) 的精度要求，实测 double 也可以通过。
实现
可能具体细节和上面不完全相同，也比较乱。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <vector>
#include <cassert>
#include <cmath>
using namespace std;
#define LOG(f...) fprintf(stderr, f)
using ll = long long;
template<class T> void read(T &x) {
char ch; x = 0;
int f = 1;
while (isspace(ch = getchar()));
if (ch == '-') ch = getchar(), f = -1;
do x = x * 10 + (ch - '0'); while(isdigit(ch = getchar()));
x *= f;
}
template<class T, class ...A> void read(T &x, A&... args) { read(x); read(args...); }
using fp = long double;
const int N = 51;
char s[N], ans[N];
int kmp[N][26], fa[N];
int kmp_valued[N], kmp_c0[N];
fp dp[N][N][N], res_len[N];
int n;
ll k;
bool is_lyndon(char *s, int len = -1) {
if (len == -1) len = strlen(s + 1);
for (int i = 2; i <= len; ++i) {
for (int j = 0; j <= len - i; ++j) {
if (s[i + j] < s[1 + j]) return false;
if (s[i + j] > s[1 + j]) goto correct;
}
return false;
correct:;
}
return true;
}
fp DP(char *s) {
memset(dp, 0, sizeof(dp));
memset(res_len, 0, sizeof(res_len));
int len = strlen(s + 1);
if (len == n)
return is_lyndon(s);
for (int i = 2; i <= len; ++i) {
for (int j = 0; j <= len - i; ++j)
if (s[i + j] > s[1 + j]) break;
else if (s[i + j] < s[1 + j]) return 0;
}
fa[1] = 0;
kmp[0][s[1] - 'a'] = 1;
for (int i = 0; i != s[1] - 'a'; ++i)
kmp[0][i] = -1;
for (int i = 1; i <= len; ++i) {
memcpy(kmp[i], kmp[fa[i]], sizeof(kmp[0]));
if (i != len) {
kmp[i][s[i + 1] - 'a'] = i + 1;
fa[i + 1] = kmp[fa[i]][s[i + 1] - 'a'];
}
for (int j = 25; j > 0; --j)
if (kmp[i][j]) {
for (int k = 0; k != j; ++k)
kmp[i][k] = -1;
break;
}
}
memset(kmp_valued, -1, sizeof(kmp_valued));
memset(kmp_c0, 0, sizeof(kmp_c0));
for (int i = 0; i <= n; ++i)
for (int j = 0; j < 26; ++j)
if (kmp[i][j] == 0) ++kmp_c0[i];
else if (kmp[i][j] > 0) kmp_valued[i] = kmp[i][j];
dp[0][len][0] = 1;
for (int i = 0; i < n - len; ++i) {
for (int j = 0; j <= len; ++j) {
for (int k = 0; k <= i; ++k) {
if (kmp_valued[j] != -1)
dp[i + 1][kmp_valued[j]][k + (kmp_valued[j] == len)] += dp[i][j][k];
dp[i + 1][0][k] += dp[i][j][k] * kmp_c0[j];
}
}
}
for (int j = 0; j <= len; ++j) {
int u = j;
bool flag = true;
int cnt = 0;
for (int i = 1; i <= len; ++i) {
if (kmp[u][s[i] - 'a'] == -1) { flag = false; break; }
u = kmp[u][s[i] - 'a'];
if (u == len) ++cnt;
}
if (!flag) continue;
for (int k = 0; k <= n - len; ++k) {
if (k + cnt == 0) continue;
fp val = fp(1) / (k + cnt);
for (int i = k; i <= n - len; ++i)
res_len[i + len] += val * dp[i][j][k];
}
}
for (int i = 1; i <= len; ++i) {
bool flag = true;
for (int j = i + 1; j <= len; ++j)
if (s[j] != s[j - i]) { flag = false; break; }
res_len[i] = flag && is_lyndon(s, i);
}
for (int i = len + 1; i <= n; ++i) {
for (int j = 1, li = i / 2; j <= li; ++j)
if (i % j == 0)
res_len[i] -= res_len[j] * (fp(j) / i);
}
return accumulate(res_len + len, res_len + n + 1, fp(0));
}
int len_s;
ll solve(int p, ll cnt, bool greater) {
ans[p] = 0;
ll orig_cnt = cnt;
if (!s[p] || greater) {
fp val = DP(ans);
if (val + 0.5 < cnt) return ll(val + 0.5);
if (fabsl(val - cnt) < 0.5 && p == n + 1)
puts(ans + 1), exit(0);
}
cnt -= (greater || p > len_s) && is_lyndon(ans);
if (!cnt) {
puts(ans + 1);
exit(0);
}
for (ans[p] = max('a', greater ? 'a' : s[p]); ans[p] <= 'z'; ++ans[p]) {
fp val = solve(p + 1, cnt, greater || (ans[p] > s[p]));
cnt -= ll(val + 0.5);
}
ans[p] = 0;
return orig_cnt - cnt;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
scanf("%d%lld", &n, &k);
scanf("%s", s + 1);
len_s = strlen(s + 1);
solve(1, k, false);
puts("-1");
return 0;
}