SP26182 JC15D - Perfect Superstring

**完美超串** Satria 是个聪明人，他在理解二进制系统后，立即提出了一个新挑战！挑战是：给他一个二进制字符串 $S$，他会找出一个不是 $S$ 的子串的最短二进制字符串 $B$。但人的智力总有极限，Satria 若检查的 $S$ 的子串长度超过 $N$，他的脑力就会疲惫。因此，如果二进制字符串 $S$ 包含了所有可能的长度为 $N$ 的二进制字符串 $B$，他就无法再找出这样的 $B$。 Gunawan 知道了这个挑战以及 Satria 的智力极限，决定制作一个完美的长度为 $N$ 的超串。他将所有可能的二进制字符串 $B$ 写下来并连接在一起。例如，若他想制作长度为 2 的完美超串，他将 {0, 1, 00, 01, 10, 11} 拼接成 0100011011。然而，由于 Satria 的智力极限很高，Gunawan 的方法在高阶中效率低下，但他坚持要按照这个方法完成任务。 在 Gunawan 写下了 $K$ 位二进制字符串后，Tjandra 对他的认真态度感到好奇，问道： Tjandra："你在做什么？" Gunawan："我在解决 Satria 的挑战。" Tjandra："听起来有趣，你能解释一下吗？" （Gunawan 解释了挑战的内容） Tjandra："哇，太有趣了。你是怎么解决这个问题的？" （Gunawan 解释了他的方法） Tjandra："那效率太低了。事实上，只需要连接长度为 $N$ 的所有可能的二进制字符串就行了，长度小于 $N$ 的子串最终都会被包括在内。例如，如果要制作长度为 2 的完美超串，字符串 0100011011 太长了，其实只需要连接 {00, 01, 10, 11} 得到 00011011 就够了，依然是长度为 2 的完美超串。" Gunawan："哇，这确实更短！以前没想到过，这是最短的吗？" Tjandra："不，还有更短的。例如，在 000110011 中，子串 11 出现两次，可以删掉一个 '1'，仍然满足长度为 2 的完美超串。" Gunawan："没错，我不想浪费精力。我希望能得到最短长度的完美超串。" Tjandra："很遗憾，目前没有简便的方法来生成这样一个最短的完美超串，但我知道有人可以用现代计算机来帮你实现。" （Tjandra 从口袋里掏出他的旧手机，准备联系你求助） Gunawan："等一下，我已经写下了 $K$ 位，我不想从头开始删掉它们。" Tjandra："好吧 -\_- 我会考虑这一点的。" 于是，Tjandra 用他的旧手机打电话向你求助，因为他知道你精于处理字符串。你能帮他们实现吗？

第一行输入一个整数 $N$，表示 Satria 挑战中的完美超串的阶数。 第二行输入两个整数 $K$ 和一个字符串 $X$，$K$ 表示 Gunawan 已经写下的二进制字符串的长度，$X$ 是该二进制字符串本身。

第一行输出一个最短的以 $X$ 开头的长度为 $N$ 的完美超串，记为长度 $L$。 第二行输出一个长度为 $L$ 的二进制字符串，其是满足条件的完美超串。

- $1 \leq N \leq 10$ - $0 \leq K \leq 10^5$ - 字符串 $X$ 的长度为 $K$，即 $|X| = K$。当 $K=0$ 时，$X$ 可以是空串。 **样例 1** 输入 ``` 1 1 0 ``` 输出 ``` 2 01 ``` **样例 2** 输入 ``` 1 1 1 ``` 输出 ``` 2 10 ``` **样例 3** 输入 ``` 2 2 01 ``` 输出 ``` 5 01100 ``` **样例 4** 输入 ``` 3 3 110 ``` 输出 ``` 10 1101000111 ``` **样例 5** 输入 ``` 3 3 110 ``` 输出 ``` 10 1100010111 ``` **样例 4（及 5）解释** 在样例 4 中，字符串 1101000111 以 110 开头：\[110\]1000111，因此 Gunawan 不需要将他之前写的数字删掉。 它满足长度为 3 的完美超串，因为它包含所有可能的长度为 3 的二进制字符串： 0: 1101000111 1: **1**101000111 00: 1101**00**0111 01: 11**01**000111 10: 1**10**1000111 11: **11**01000111 000: 1101**000**111 001: 11010**001**11 010: 11**010**00111 011: 110100**011**1 100: 110**100**0111 101: 1**101**000111 110: **110**1000111 111: 1101000**111** 注意，同样长度的字符串可能不止一种解法，如样例 5 中的 1100010111，也是另一个满足条件的最短完美超串。 **本翻译由 AI 自动生成**