python/TangDou/AcWing/EulerPath/400.md

## [$AcWing$ $400$ 太鼓达人](https://www.acwing.com/problem/content/402/)


### 一、题目描述
太鼓达人的鼓坏了，现在 $vani$ 来修鼓。

鼓的主要元件是 $M$ 个围成一圈的传感器。每个传感器都有开和关两种工作状态，分别用$1$和$0$表示。

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

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

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

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


**输入格式**
一个整数 $K$。

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

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

**数据范围**
$2≤K≤11$

**输入样例**：
```cpp {.line-numbers}
3
```

**输出样例**：
```cpp {.line-numbers}
8 00010111
```

### 二、解题思路
很显然，第一问的答案就是 $2^n$。

第二问，构造一个有 $2^{n-1}$个节点的图，对应 $2^{n-1}$个 $n-1$ 位二进制数。从代表数 $k$ 的节点($0<=k<2^{n-1}$)向代表数$(k<<1)\&(1<<(n-1))$的节点 和 代表数$((k<<1)+1)\&(1<<(n-1))$的节点分别连一条边。可以发现这样的图中，所有点的入度和出度都是 $2$，因此这是一个欧拉图。

因此我们从 $0$ 号点开始 $dfs$ 寻找一个欧拉回路，回溯的时候记录到栈中，最后倒序输出即可。

因为要求字典序最小，$dfs$ 的时候要注意搜索顺序，先走 $0$ 边，再走 $1$ 边。这个算法寻找欧拉回路，每个点、每条边只访问一次，是 $O(V+E)$级别的。

时间复杂度 $O(2^n)$，预计得分 $100$ 分。


和上一题一样，其实，000到001，其实00是不变的，可以抽象成点，而000，001都是只有一个，可以抽象成边，那么这题就可以做出来了，以0——2^（n-1)-1为编号建立一棵树，共2^（n-1)个节点，如果在某个节点后面添加一个0或者1,再去掉最高位，得到下一个节点，两节点之间连一条有向边。图中每条边就表示了一个数，共有2^n个数，各不相同！题目要求字典序最小，则从2^(n-1-1节点开始，并且每个节点先连加0的边，后连加1的边，这样的话，就能保证最终的字典序最小。还是欧拉回路，都是一个模型，算法也就那个一个。只是这里，为什么，我取模了，提交OJ反而会快10几Ms,这一点，我不明白的！