在最终结果里面，每一个n位二进制数都会连接ta前面的二进制数的后n-1位。
所以构建欧拉图的时候只需要$2^{n-1}$个点，然后用n位二进制数当成边，连接ta前n-1位和后n-1位，然后跑一次欧拉回路就行了（欧拉回路证明略）。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 2000, M = 5000;

int n;
int tot, Head[N], ver[M], Next[M], id[M];
int siz, path[M];

void add(int x, int y, int z) {
    tot++;
    ver[tot] = y;
    id[tot] = z;
    Next[tot] = Head[x];
    Head[x] = tot;
}

void dfs(int x, int pre) {
    for (int i = Head[x]; i; i = Head[x]) {
        int y = ver[i]; 
        Head[x] = Next[i];
        dfs(y, id[i]);
    }
    path[++siz] = pre;
}

int main() {
    cin >> n;
    for (int i = (1 << n) - 1; i >= 0; i--) {
        int x = i >> 1;
        int y = i & ((1 << (n - 1)) - 1);
        add(x, y, i);
    }
    dfs(0, 0); siz--;
    printf("%d ", (1 << n));
    for (int i = 1; i < n; i++) putchar('0');
    for (int i = siz; i >= n; i--) printf("%d", path[i] & 1);
    puts("");
    return 0;
}