题目描述

太鼓达人的鼓坏了，现在 vani 来修鼓。

鼓的主要元件是 $M$ 个围成一圈的传感器。

每个传感器都有开和关两种工作状态，分别用 1 和 0 表示。

显然，从不同的位置出发沿顺时针方向连续检查 $K$ 个传感器可以得到 $M$ 个长度为 $K$ 的 01 串。

Vani 知道这 $M$ 个 01 串应该是互不相同的。

而且鼓的设计很精密，$M$ 会取到可能的最大值。

现在 Vani 已经了解到了 $K$ 的值，他希望你求出 $M$ 的值，并给出字典序最小的传感器排布方案。

输入格式

一个整数 $K$。

输出格式

一个整数和一个二进制串，由一个空格分隔，分别表示可能的最大的 $M$ 以及字典序最小的排布方案。

字符 0 表示关，1 表示开，你输出的串的第一个字和最后一个字是相邻的。

样例

3

8 00010111

样例解释

输入

$K = 3$

输出

$M = 8$，方案为 00010111

验证

传感器围成一圈，方案 00010111 长度为 8。 从每个位置开始连续取 3 位（可循环）：

1. 位置 1: 000
2. 位置 2: 001
3. 位置 3: 010
4. 位置 4: 101
5. 位置 5: 011
6. 位置 6: 111
7. 位置 7: 110（注意循环，7,8,1）
8. 位置 8: 100（8,1,2） 这 8 个串互不相同，且包含了所有可能的 3 位二进制串（共 $2^3 = 8$ 个）。所以 $M$ 取到了最大值 8。

字典序最小：所有方案中 00010111 字典序最小。

数据范围

• $2 \le K \le 11$

算法分析

这是一个德布鲁因序列（De Bruijn sequence） 问题。

德布鲁因序列

对于给定的字母表大小为 $n$（这里是 2，0 和 1）和子串长度 $K$，德布鲁因序列是一个循环序列，其中每个可能的长度为 $K$ 的子串恰好出现一次。

德布鲁因序列的长度为 $n^K$，即 $2^K$。

本题要求 $M$ 最大，显然 $M$ 最大为 $2^K$（因为一共有 $2^K$ 个不同的长度为 $K$ 的 01 串，且每个串在循环序列中只能出现一次）。所以 $M = 2^K$。

我们需要构造一个长度为 $2^K$ 的 01 循环序列，使得所有长度为 $K$ 的 01 串恰好出现一次，并且字典序最小。

构造方法

可以通过欧拉回路或哈密顿回路构造。

将每个长度为 $K-1$ 的 01 串看作一个节点，从节点 $u$ 到节点 $v$ 有一条有向边，当且仅当 $v$ 的前 $K-2$ 位等于 $u$ 的后 $K-2$ 位，并且 $v$ 的最后一位是 0 或 1。这样，每条边对应一个长度为 $K$ 的串（$u$ 的 $K-1$ 位加上 $v$ 的最后一位）。

例如，$K=3$，节点为所有 2 位串：00,01,10,11。 边：

• 从 00 到 00（添加 0）得到串 000
• 从 00 到 01（添加 1）得到串 001
• 从 01 到 10（添加 0）得到串 010
• 从 01 到 11（添加 1）得到串 011
• 从 10 到 00（添加 0）得到串 100
• 从 10 到 01（添加 1）得到串 101
• 从 11 到 10（添加 0）得到串 110
• 从 11 到 11（添加 1）得到串 111

这样，每个长度为 $K$ 的串对应一条边。问题转化为求一条欧拉回路，经过每条边恰好一次，并且起点和终点相同。

因为每个节点的入度和出度都是 2（每个节点可以添加 0 或 1 得到两个后继，也可以由两个前驱添加一位得到），所以存在欧拉回路。

为了字典序最小，我们在 DFS 时优先走 0 边（即添加 0），再走 1 边。

实现细节

• 节点可以用 $K-1$ 位二进制数表示，范围 $0 \sim 2^{K-1}-1$。

• 边不需要显式存储，在 DFS 时，当前节点 $u$，可以扩展到 (u << 1) & mask（添加 0）和 (u << 1) & mask | 1（添加 1），其中 $mask = 2^{K-1} - 1$。

• 记录每条边是否访问过。由于每条边对应一个长度为 $K$ 的串，我们可以用 $u$ 和添加的位来表示边，但更简单的方法是：用 $u$ 和下一个节点 $v$ 来表示边。由于 $v$ 由 $u$ 和添加的位唯一确定，所以我们可以用 $u$ 和添加的位来标记访问。但这里节点数少，我们可以用 $vis[u][0]$ 和 $vis[u][1]$ 表示从 $u$ 添加 0 或 1 的边是否访问过。

• 欧拉回路经过的边数为 $2^K$，我们记录每条边添加的位（0 或 1），最终序列长度为 $2^K$，但最后一个节点会多出一位？实际上，欧拉回路经过 $2^K$ 条边，每条边贡献一位（即添加的位），但起点节点 $u_0$ 的 $K-1$ 位也需要包含在序列中。所以总序列长度为 $2^K + K - 1$？不对，我们最终需要的是一个循环序列，长度为 $M = 2^K$。在欧拉回路中，如果我们取起点节点的 $K-1$ 位作为前 $K-1$ 位，然后依次添加每条边的最后一位，这样得到的序列长度为 $2^K + K - 1$，但它是线性的，不是循环的。由于是循环序列，我们可以只取前 $2^K$ 位，因为后 $K-1$ 位会和前 $K-1$ 位重复（循环）。

  实际上，标准做法是：从节点 $0$（$K-1$ 个 0）开始 DFS，记录每条边的添加位，最后输出这些位组成的序列，长度就是 $2^K$。因为循环序列中，每个节点的 $K-1$ 位信息被隐含在边中。

  具体实现时，我们 DFS 回溯时记录添加位，最终序列是这些添加位的逆序。但这样得到的序列长度是 $2^K$，并且是一个合法的德布鲁因序列。

算法步骤

1. 设 $n = 2^{K-1}$，节点编号 $0 \sim n-1$。
2. 从节点 $0$ 开始 DFS，优先走添加 0 的边，然后添加 1。
3. 用栈记录欧拉路径的边（添加的位）。
4. 因为每个节点有两条出边，我们需要标记边是否访问过。可以用二维数组 $vis[node][bit]$ 表示从 $node$ 添加 $bit$ 的边是否访问过。
5. DFS 回溯时将添加的位压入栈。
6. 最终栈中元素从栈底到栈顶就是所求序列（长度为 $2^K$）。
7. 注意：由于起点是 $K-1$ 个 0，我们需要在序列开头补上 $K-1$ 个 0 吗？实际上，我们记录的边添加位已经包含了所有信息。最终序列就是这些添加位构成的，长度为 $2^K$，并且满足条件。验证：对于 $K=3$，按照上述算法，从节点 00 开始，优先走 0 边到 00（添加 0），然后继续… 最终得到的添加位序列为 00010111，正是样例输出。所以不需要额外补 0。

复杂度

• 节点数 $2^{K-1} \le 2^{10} = 1024$。
• 边数 $2^K \le 2048$。
• DFS 复杂度 $O(2^K)$，可接受。

样例验证

对于 $K=3$：

• 节点：00(0),01(1),10(2),11(3)
• 从节点 0（00）开始 DFS：
  • 走 0 边到节点 0（00），添加 0，递归。
    • 从节点 0 走 0 边到节点 0，但边已访问？不，第一次访问节点 0 时，我们标记了从节点 0 添加 0 的边，所以第二次不能再走。
    • 走 1 边到节点 1（01），添加 1，递归。
      • 从节点 1 走 0 边到节点 2（10），添加 0，递归。
        • 从节点 2 走 0 边到节点 0（00），添加 0，递归。
          • 节点 0 的两条边都已访问，回溯。
        • 添加位 0 入栈。
        • 从节点 2 走 1 边到节点 1（01），添加 1，递归。
          • 节点 1 的两条边都已访问，回溯。
        • 添加位 1 入栈。
      • 添加位 0 入栈。
      • 从节点 1 走 1 边到节点 3（11），添加 1，递归。
        • 从节点 3 走 0 边到节点 2（10），添加 0，递归。
          • 节点 2 的两条边都已访问，回溯。
        • 添加位 0 入栈。
        • 从节点 3 走 1 边到节点 3（11），添加 1，递归。
          • 节点 3 的两条边都已访问，回溯。
        • 添加位 1 入栈。
      • 添加位 1 入栈。
    • 添加位 1 入栈。
  • 添加位 0 入栈。

栈中从栈底到栈顶：0,1,1,1,0,1,0,0 即 01110100，反向（因为回溯入栈）得到 00010111，正是答案。

总结

本题是德布鲁因序列的构造问题，通过欧拉回路求解，优先走 0 边保证字典序最小。注意 $M$ 的最大值为 $2^K$。