CF1065G Fibonacci Suffix

我们再次定义斐波那契字符串序列： $F(0) = $ 0，$F(1) = $ 1，$F(i) = F(i - 2) + F(i - 1)$，其中加号表示两个字符串的连接。 我们将字符串 $F(i)$ 的所有后缀按字典序排序后得到的序列记为 $A(F(i))$。例如，$F(4)$ 为 01101，$A(F(4))$ 为以下序列：01，01101，1，101，1101。该序列中的元素从 $1$ 开始编号。 你的任务是输出 $A(F(n))$ 中第 $k$ 个元素的前 $m$ 个字符。如果该后缀长度小于 $m$，则输出整个后缀。

输入仅一行，包含三个整数 $n$、$k$ 和 $m$（$1 \le n, m \le 200$，$1 \le k \le 10^{18}$），分别表示你需要考虑的斐波那契字符串的编号、$A(F(n))$ 中元素的编号，以及你需要输出的字符数。 保证 $k$ 不会超过 $F(n)$ 的长度。

输出 $A(F(n))$ 中第 $k$ 个元素的前 $m$ 个字符。如果该元素长度小于 $m$，则输出整个元素。

由 ChatGPT 4.1 翻译