1532：太鼓达人

题目描述

七夕祭上，Vani 牵着 cl 的手，在明亮的灯光和欢乐的气氛中愉快地穿行。这时，在前面忽然出现了一台太鼓达人机台，而在机台前坐着的是刚刚被精英队伍成员 XLk、Poet_shy 和 lydrainbowcat 拯救出来的的 applepi。看到两人对太鼓达人产生了兴趣，applepi 果断闪人，于是 cl 拿起鼓棒准备挑战。然而即使是在普通难度下，cl 的路人本性也充分地暴露了出来。一曲终了，不但没有过关，就连鼓都不灵了。Vani 十分过意不去，决定帮助工作人员修鼓。

鼓的主要元件是 $M$ 个围成一圈的传感器。每个传感器都有开和关两种工作状态，分别用 $1$ 和 $0$ 表示。显然，从不同的位置出发沿顺时针方向连续检查 $K$ 个传感器可以得到 $M$ 个长度为 $K$ 的 $01$ 串。Vani 知道这 $M$ 个 $01$ 串应该是互不相同的。而且鼓的设计很精密，$M$ 会取到可能的最大值。现在 Vani 已经了解到了 $K$ 的值，他希望你求出 $M$ 的值，并给出字典序最小的传感器排布方案。

输入格式

一个整数 $K$。

输出格式

一个整数 $M$ 和一个二进制串，由一个空格分隔。表示可能的最大的 $M$，以及字典序最小的排布方案，字符 0 表示关，1 表示开。你输出的串的第一个字和最后一个字是相邻的。

样例

样例输入 #1

3

样例输出 #1

8 00010111

样例解释 #1

• $K=3$，传感器围成一圈。
• 可能的最大 $M$ 是 $8$，因为长度为 $3$ 的二进制串共有 $2^3=8$ 种。
• 一种排布方案为 00010111，长度为 $8$。
• 从每个位置开始取连续 $3$ 位（循环）：
  1. 位置 $1$: 000
  2. 位置 $2$: 001
  3. 位置 $3$: 010
  4. 位置 $4$: 101
  5. 位置 $5$: 011
  6. 位置 $6$: 111
  7. 位置 $7$: 110
  8. 位置 $8$: 100（注意最后两位和第一位连起来）
• 这 $8$ 个串互不相同，且包含了所有可能的 $3$ 位二进制串。
• 方案 00010111 是字典序最小的（即 $0$ 尽可能多在前）。

数据范围

对于全部测试点，$2 \le K \le 11$。

时空限制

• 时间限制：1000 ms
• 内存限制：131072 KB

注意：本题是求 de Bruijn 序列。对于给定的 $K$，最大 $M = 2^K$。我们需要构造一个长度为 $2^K$ 的 $01$ 环，使得每个长度为 $K$ 的 $01$ 串恰好出现一次（作为环上的连续 $K$ 个字符）。构造方法可以转化为求欧拉回路：将每个长度为 $K-1$ 的 $01$ 串看作顶点，从顶点 $u$（即一个 $K-1$ 位串）通过添加一个位 $0$ 或 $1$ 得到下一个顶点 $v$（即 $u$ 去掉最高位，再在末尾添加新位），这样构成一条有向边。这样图有 $2^{K-1}$ 个顶点，每个顶点有两条出边（添加 $0$ 或 $1$）和两条入边（从两个前缀转移而来）。该图存在欧拉回路，回路长度为 $2^K$，对应一个 de Bruijn 序列。要求字典序最小，即在 DFS 或 Hierholzer 算法中优先选择添加 $0$ 的边。注意输出序列时，需要从全 $0$ 的顶点开始，并且最后 $K-1$ 位要与开头 $K-1$ 位相同（因为是环）。由于 $K \le 11$，顶点数最多 $2^{10}=1024$，边数 $2^K \le 2048$，可以轻松求解。