题意

对于一个长度为 $n$ 的字符串 $s$，我们建立一张 $n$ 个节点的带权无向图。每个节点代表一个后缀，两个节点之间的边权为这两个后缀的 LCP 长度。定义字符串 $s$ 的代价为对应图的最大生成树边权之和。

给定 $n, k$，求所有长度为 $n$，字符集为小写字母集合的字符串中，代价第 $k$ 小的是哪个。如果并列多个，任意输出一个。

$\sum n \le 4\times 10^5, k \le 10^{15}$。

题解

对于长度为 $n$ 的串，共有 $26^{n}$ 个，$n$ 稍微大一点的时候，这个数目就远大于 $k$ 了。因此我们猜测，当 $n$ 充分大的时候，第 $k$ 小和最小值应当相同。

先不急着思考怎么构造最小值，我们来分析一下“充分大”的界限在哪里：假设一个字符串出现了 $c$ 种不同字符，那么我们做单表替换，可以得到 $\frac{26!}{(26-c)!}$ 种不同的字符串。这个值关于 $c$ 单调递增，而当 $c\ge 12$ 时，这个值就已经超过 $10^{15}$ 了。因此，这告诉我们，“充分大”指的是 $n\ge 12$ 的情况。

而 $n\le 11$ 似乎是 trivial 的情况：我们考虑枚举 $\mathrm{Bell}(n)$ 中集合划分情况，每个集合内部的字符相同。那么方案数容易计算，查询的时候枚举一下答案即可。

这里我们顺便可以思考一下如何计算最大生成树：因为后缀的 LCP 在后缀数组上是一段区间的 height 最小值（设 height 数组为 $ht_i$），所以最大生成树必定是连接所有 $(sa_i, sa_{i + 1})$ 边，也即 $\sum ht_i$。根据经典结论，我们知道这就是 $\binom{n + 1}{2}-C$，其中 $C$ 表示 $s$ 的本质不同子串个数。因此计算代价迎刃而解。

接下来需要解决 $n\ge 12$ 的 case：求最小值也即最大化本质不同子串数量。先对答案的下界进行估计：枚举子串长度 $i$，那么至多有 $26^i$ 种不同子串，而 $s$ 种有 $n - i + 1$ 个这样的子串，因此答案 $\ge \sum\limits_{i = 1}^{n} \min(26 ^ i, n - i + 1)$。

这个下界取的到吗？直觉是猜测一定能取到。我们找到一个 $k$，使得 $26 ^ k + k - 1 \le n < 26 ^ {k + 1} + k$，那么目标就是所有长度 $< k$ 的都出现至少一次，而所有长度 $\ge k$ 的两两不同。

当 $n = 26 ^ k + k - 1$ 时，这是一个经典问题：我们考虑建 $26 ^ {k - 1}$ 个点，对于每个长度为 $k$ 的字符串，从前 $k - 1$ 个字符对应的点连一条边到后 $k - 1$ 个字符对应的点，构造一条欧拉回路即可不重不漏地遍历所有的子串。（这个序列又称为 De Bruijn 序列。）

当 $n > 26 ^ k + k - 1$ 时事情变得不太一样了。如果我们直接构造 $k + 1$ 的图，取长度为 $n$ 的前缀，这样不一定是最优的。我们还是希望在 $k$ 的图上找一条路径，然而直接找似乎并不简单。

考虑先拿出 $k - 1$ 的图，跑出一条欧拉回路。这条欧拉回路对应了 $k$ 的图上的一条哈密顿回路。我们删掉从全 $\texttt{a}$ 串出发的那条边，变成一条以全 $\texttt{a}$ 串结尾的路径。接下来以这个全 $\texttt{a}$ 串为起点，在 $k$ 的图上跑欧拉回路。我们为了使所有的子串不重复出现，还要把那条哈密顿路径上的对应边删掉。经过尝试可以发现一定能构造出长度为 $26^{k + 1} + k - 1$ 的路径（只有一个点的自环取不到），取长度为 $n$ 的前缀就必定最优了。

时间复杂度 $\mathcal O(\mathrm{Bell(m)}m^2+n|\Sigma|)$，其中 $m = 11$，$|\Sigma| = 26$。

赛后没多久就调出来了。太可惜了。

::::success[参考实现]

#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
template <class T>
using Ve = vector<T>;
#define ALL(v) (v).begin(), (v).end()
#define pii pair<ll, ll>
#define rep(i, a, b) for(ll i = (a); i <= (b); ++i)
#define per(i, a, b) for(ll i = (a); i >= (b); --i)
#define pb push_back
bool Mbe;
ll read() {
    ll x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
void write(ll x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
const ll N = 1e6 + 9, INF = 1e18;
ll n, K, C[30][30], a[30], pw26[10];
ll Add(ll x, ll y) {
    return min(x + y, INF);
}
ll Mul(ll x, ll y) {
    if(x <= INF / y) return x * y;
    return INF;
}
Ve<ll> precalc[30][109];
ll sum[30], pc[30][109];
void dfs(ll x, ll c) {
    if(x == n + 1) {
        ll cnt = 0;
        Ve<ull> hsh;
        rep(i, 1, n) {
            ull h = 0;
            rep(j, i, n) h = h * 131 + a[j], hsh.pb(h);
        }
        sort(ALL(hsh));
        cnt = unique(ALL(hsh)) - hsh.begin();
        ll ways = C[26][c];
        pc[n][cnt] += ways;
        if(precalc[n][cnt].empty()) {
            rep(i, 1, n) precalc[n][cnt].pb(a[i]);
        }
        return ;
    }
    rep(i, 1, c + 1) a[x] = i, dfs(x + 1, max(i, c)), a[x] = 0;
}
Ve<pii> to[N], es[N];
ll tope[N], ord[N], len;
void dfs1(ll x) {
    while(tope[x] < to[x].size()) {
        auto [y, w] = to[x][tope[x]]; ++tope[x];
        dfs1(y);
    }
    ord[++len] = x;
}
void dfs2(ll x) {
    while(tope[x] < es[x].size()) {
        auto [y, w] = es[x][tope[x]]; ++tope[x];
        dfs2(y);
    }
    ord[++len] = x;
}
void solve() {
    n = read(), K = read();
    if(n <= 11) {
        per(i, 100, 1) {
            if(pc[n][i] >= K) {
                cout << n * (n + 1) / 2 - i << "\n";
                rep(j, 0, n - 1) cout << (char)(precalc[n][i][j] + 'a' - 1);
                cout << "\n";
                break;
            }
        }
        return ;
    } 
    if(n <= 26) {
        cout << 0 << "\n";
        rep(i, 1, n) cout << (char)(i + 'a' - 1);
        cout << "\n";
        return ;
    }
    ll k = 0, now = 1;
    while(n >= now * 26 + k) now *= 26, ++k;
    ll ans = 0; now = 1;
    rep(i, 1, n) now = Mul(now, 26), ans += min(now, n - i + 1);
    ans = n * (n + 1) / 2 - ans;
    cout << ans << "\n";
    now = 1;
    K = k;
    rep(i, 1, k - 1) now *= 26;
    rep(i, 0, now * 26 + 1) to[i].clear(), es[i].clear();
    Ve<ll> res;
    Ve<ll> realord;
    if(K > 1) {
        rep(i, 0, now - 1) {
            ll top = i / pw26[K - 2] % 26;
            ll ni = (i - top * pw26[K - 2]) * 26;
            rep(j, 0, 25) {
                ll nj = ni + j;
                nj %= now;
                to[i].pb({nj, j});
            }
            tope[i] = 0;
        }
        len = 0;
        dfs1(0);
        reverse(ord + 1, ord + len + 1);
        per(i, K - 2, 0) realord.pb(ord[1] / pw26[i] % 26);  
        rep(i, 1, len - 1) {
            ll u = ord[i], v = ord[i + 1];
            rep(j, 0, (ll)to[u].size() - 1) {
                if(to[u][j].first == v) {
                    realord.pb(to[u][j].second);
                    break;
                }
            }
        }
    }
    else {
        len = 26;
        rep(i, 0, 25) realord.pb(i);
        realord.pb(0);
    }
    now *= 26;
    rep(i, 0, now - 1) {
        ll top = i / pw26[K - 1] % 26;
        ll ni = (i - top * pw26[K - 1]) * 26;
        rep(j, 0, 25) {
            ll nj = ni + j;
            nj %= now;
            es[i].pb({nj, j});
        }
        tope[i] = 0;
    }
    Ve<ll> go;
    rep(i, 0, (ll)realord.size() - 1) {
        if(i + K - 1 >= (ll)realord.size()) break;
        ll num = 0;
        rep(j, 0, K - 1) num = num * 26 + realord[i + j];
        go.pb(num);
    }
    go.pb(0);
    rep(i, 1, (ll)go.size() - 2) {
        ll u = go[i], v = go[i + 1];
        rep(j, 0, (ll)es[u].size() - 1) {
            if(es[u][j].first == v) {
                es[u].erase(es[u].begin() + j);
                break;
            }
        }
    }
    len = 0;
    dfs2(0);
    res = realord;
    res.erase(res.begin());
    res.pb(0);
    reverse(ord + 1, ord + len + 1);
    rep(i, 1, len - 1) {
        ll u = ord[i], v = ord[i + 1];
        rep(j, 0, (ll)es[u].size() - 1) {
            if(es[u][j].first == v) {
                res.pb(es[u][j].second);
                break;
            }
        }
    }
    res.resize(n);
    for(ll x : res) cout << (char)(x + 'a');
    cout << "\n";
}
bool Med;
int main() {
    cerr << fabs(&Med - &Mbe) / 1048576.0 << "MB\n";
    ll T = read();
    pw26[0] = 1;
    rep(i, 1, 6) pw26[i] = pw26[i - 1] * 26;
    rep(i, 0, 26) {
        C[i][0] = 1;
        rep(j, 1, i) C[i][j] = Add(C[i - 1][j], C[i - 1][j - 1]);
    }
    rep(i, 1, 26) {
        rep(j, 1, i) C[26][i] = Mul(C[26][i], j);
    }
    rep(i, 1, 11) n = i, dfs(1, 0);
    rep(i, 1, 11) {
        per(j, 100, 1) pc[i][j] = Add(pc[i][j], pc[i][j + 1]);
    }
    while(T--) solve();
    cerr << "\n" << clock() * 1.0 / CLOCKS_PER_SEC * 1000 << "ms\n";
    return 0;
}

::::