题目理解

我们定义：

• 有界单词：存在 $0 < l < |S|$，使得长度为 $l$ 的前缀 = 长度为 $l$ 的后缀。
• 无界单词：不存在这样的 $l$。

换句话说，有界单词就是 存在非零的 border（KMP 中的概念），无界单词就是 没有非零的 border。

---

问题转化

长度为 $N$ 的字符串，由 a 和 b 组成，问：

1. 无界单词的个数。
2. 无界单词中字典序第 $K$ 小的。

---

思路

1. 无界单词的计数

设 $f(n)$ 表示长度为 $n$ 的无界单词的数量。
总单词数 $= 2^n$。

关键性质：
一个字符串有非零 border 当且仅当它的最短周期 $p < n$，且 $p$ 整除 $n$。
更确切地说，一个字符串的最小周期 $p$ 与它的最长 border 长度 $b$ 有关系：$p + b = n$。

无界单词就是 最小周期 = n 的单词。

---

容斥/递推方法

设 $f(n)$ 表示长度为 $n$ 的无界单词数。
所有长度为 $n$ 的单词可以分为：

• 最小周期 = $n$ 的（无界单词）
• 最小周期 = $d$ 的，其中 $d$ 是 $n$ 的真因子。

于是： $2^n = \sum_{d|n} f(d)$ 因为对于每个最小周期 $d$，它对应一个长度为 $n$ 的串，由长度为 $d$ 的无界单词重复 $n/d$ 次得到。

---

由莫比乌斯反演： $f(n) = \sum_{d|n} \mu(d) \cdot 2^{n/d}$ 其中 $\mu$ 是莫比乌斯函数。

这样我们可以 $O(\sqrt{n})$ 枚举 $n$ 的因子，计算 $f(n)$。

---

2. 构造第 $K$ 小的无界单词

我们要按字典序构造第 $K$ 小的无界单词。

方法：
从前往后逐位确定，每次尝试放 a，然后计算以当前前缀开头的无界单词数量，如果 $K$ 大于这个数量，就改为放 b 并减少 $K$。

---

如何计算以给定前缀 $P$ 开头的无界单词数量？

设当前前缀长度为 $len$，我们要求长度为 $N$ 的无界单词且前缀是 $P$ 的数量。

考虑 $P$ 的 border 结构（KMP 的 fail 数组），这会影响后续字符的限制。

---

关键：
当我们已经确定了前 $len$ 个字符，我们要求整个串是无界的，即整个串没有非平凡的 border。
但是 border 可能跨越已确定部分和未确定部分。

---

我们可以在构造时维护一个“禁止 border 长度”的集合。
具体地，假设当前前缀是 $P[0..len-1]$，我们考虑如果整个串有一个 border 长度 $l$，这意味着：

• $P[0..l-1] = S[N-l..N-1]$。
• 如果 $l \le len$，那么 $P[0..l-1]$ 必须等于 $P[len-l..len-1]$。
• 如果 $l > len$，那么 $P[0..len-1]$ 必须等于 $S[N-l..N-l+len-1]$，并且 $S[N-l+len..N-1]$ 是未确定部分。

---

为了简化，我们可以用 动态规划 + KMP 自动机 的方法：

定义 $dp[pos][j]$ = 从位置 $pos$ 开始，当前 KMP 状态（即匹配前缀函数值）为 $j$ 时，能构成无界单词的方案数。

KMP 状态 $j$ 表示当前前缀与后缀的最长匹配长度。

---

无界条件：最终在 $pos = N$ 时，$j$ 必须等于 0（否则有非零 border）。

---

计算方式

我们预处理前缀 $P$ 的 KMP 数组 $pi[0..len-1]$，然后从 $pos = len$ 开始，KMP 状态 $j$ 就是 $pi[len-1]$（如果 $len > 0$）。

然后我们进行 DP：

• 从 $pos = len$ 到 $N$：
  • 如果 $pos = N$，则检查 $j$ 是否为 0，是则方案数 = 1，否则 0。
  • 否则，尝试两种字符 a 和 b，更新 KMP 状态，累加方案数。

这里 DP 可以用记忆化搜索，状态 $(pos, j)$，$pos$ 从 $len$ 到 $N$，$j \le pos$。

---

3. 整体算法

1. 对于每组数据 $(N, K)$：
   • 用莫比乌斯反演计算 $f(N)$。
   • 逐位构造第 $K$ 小的无界单词：
     • 从空串开始，KMP 状态 $j=0$。
     • 对于每一位，先尝试放 a，计算以当前前缀开头的无界单词数量 $cnt$。
     • 如果 $K \le cnt$，则这一位确定为 a，保持 $K$ 不变。
     • 否则，确定为 b，$K \gets K - cnt$。
     • 更新 KMP 状态。
   • 输出结果。

---

复杂度

• 计算 $f(N)$：$O(\sqrt{N})$。
• 构造第 $K$ 小的单词：每次计算方案数需要 $O(N^2)$ DP（状态数 $O(N^2)$），总复杂度 $O(N^3)$ 对于 $N \le 64$ 可接受。

---