一、题目重述与核心分析
1.1 题目要求
给你两个正整数 n 和 k，二进制字符串 Sn 的形成规则如下：
- S₁ = '0'
- 当 i > 1 时，Sᵢ = Sᵢ₋₁ + '1' + reverse(invert(Sᵢ₋₁)) 其中：
- 表示串联操作（拼接字符串）；
- reverse(x)：返回反转 x 后得到的字符串；
- invert(x)：翻转 x 中的每一位（0→1，1→0）。 要求返回 Sₙ 的第 k 位字符（题目保证 k 一定在 Sₙ 长度范围内）。
1.2 示例拆解（理解字符串生成规则）
先通过前 4 个字符串，直观理解生成逻辑，这是解题的核心前提：
- S₁ = '0' （长度 1 = 2¹ - 1）
- S₂ = S₁ + '1' + reverse(invert(S₁)) → '0' + '1' + reverse('1') → '011' （长度 3 = 2² - 1）
- S₃ = S₂ + '1' + reverse(invert(S₂)) → '011' + '1' + reverse('100') → '0111001' （长度 7 = 2³ - 1）
- S₄ = S₃ + '1' + reverse(invert(S₃)) → 长度 15 = 2⁴ - 1 关键规律：Sₙ 的长度始终是 2ⁿ - 1。这个规律是后续「分治 + 递归」解题的核心依据！
1.3 题目本质
直接生成 Sₙ 再取第 k 位，看似简单，但当 n=20 时，Sₙ 的长度为 2²⁰ - 1 = 1048575，虽不算极大，但存在「不必要的空间浪费」（我们只需要第 k 位，无需生成完整字符串）。 因此，解题的核心思路是：利用 Sₙ 的生成规律，通过分治思想，递归缩小范围，直接定位第 k 位，避免生成完整字符串。
二、核心规律推导（分治思想的关键）
对于任意 Sₙ（n > 1），其总长度为 len = 2ⁿ - 1，中间位置 mid = 2ⁿ⁻¹。 根据生成规则 Sₙ = Sₙ₋₁ + '1' + reverse(invert(Sₙ₋₁))，可得以下结论：
- 若 k == mid，则 Sₙ[k] 必定为 '1'。
- 若 k < mid，则 Sₙ[k] 等同于 Sₙ₋₁[k]，问题规模减小为求解 Sₙ₋₁ 的第 k 位。
- 若 k > mid，则 Sₙ[k] 对应于 Sₙ₋₁ 中对称位置的逆值。具体而言，对应 Sₙ₋₁ 的位置为 len(Sₙ₋₁) - (k - mid) + 1，且结果需取反（0 变 1，1 变 0）。
三、代码实现（Python）
def find_kth_bit(n: int, k: int) -> str:
# 辅助函数：计算第 n 个字符串的长度
def get_len(n):
return (1 << n) - 1
# 递归查找
def solve(n, k):
length = get_len(n)
mid = length // 2 + 1
if k == mid:
k < mid:
solve(n - , k)
:
solve(n - , length - k + ) ==
solve(n, k)
