思路与算法

构造顶点为K-1位二进制串的图，从每个顶点追加0或1并丢弃最高位，得到两条有标号出边。按0在先、1在后执行Hierholzer，回退记录边标号，最后逆序得到欧拉环。再比较所有循环旋转，输出字典序最小表示；边数为2^K。

正确性说明

一个K位串唯一对应“前K-1位顶点+最后一位边”，欧拉环每边一次就使每个K位窗口恰好出现一次。最多只有2^K个不同窗口，因此达到M上界。按边字典序的Hierholzer在可完成欧拉遍历前提下得到最小欧拉序列，最小旋转处理圆环起点，独立FKM Lyndon串构造逐字一致。K2至11的所有验收串还检查了全部窗口唯一性。

复杂度

V=2^(K-1)、E=2^K，建图用隐式两出边，Euler过程O(E)，每次比较/构造旋转O(E)，总O(E²)，本题E≤2048。额外空间O(E)含递归栈、答案及临时旋转；nextEdge初始化O(V)，不是把全部K位窗口另行存到程序中。

易错点

输出圆环本身长2^K，不额外追加开头K-1位。顺时针跨尾首的窗口也必须计入。仅输出任意de Bruijn环不够，还要求字典序最小；不能只检查去重数量而忽略字典序。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int k, mask;
vector<int> nextEdge;
string rev;
void walk(int u) {
    while (nextEdge[u] < 2) {
        int b = nextEdge[u]++;
        walk(((u << 1) | b) & mask);
        rev += char('0' + b);
    }
}
int main() {
    cin >> k;
    mask = (1 << (k - 1)) - 1;
    nextEdge.resize(mask + 1);
    walk(0);
    reverse(rev.begin(), rev.end());
    string answer = rev;
    for (size_t i = 1; i < rev.size(); ++i)
        answer = min(answer, rev.substr(i) + rev.substr(0, i));
    cout << (1 << k) << ' ' << answer << '\n';
}