( ext{Solution:})
容易发现这倒是像构造题了。而且数据范围相对宽松，样例答案又启发我们第一问的答案就应该是 (2^n,) 那么怎么构造一个串使得所有数字 (iin [0,2^n]) 都出现在这个串中呢？
我们仔细发掘一下题目性质。如果我们把每个点看成一个值：从这个点往前走 (k) 步所得到的子串在十进制下的数值，那么问题就变成了：有一些转移边，求一种构造走遍每个点恰好一次。
那这个我们显然不太会做。这是哈密顿路了，就变得很 NPC 了。
那么我们仔细想想，自己学过啥可以做类似的东西：如果可以把题目转化为走过每条边恰好一次不就成了！
那么重新抽象模型：令 (0,1) 为点的标号，以权值为边的标号。我们的目标就是走完所有边恰好一次。
那这样我们就可以直接上欧拉回路了。容易证明的是，一定存在一种方案使得 (k) 个 (0) 摆满前 (k) 个位置。
而通过这样构建的图必然存在欧拉回路，也就证明了我们上述对于第一问答案的猜想。
#include<bits/stdc++.h>
using namespace std;
const int N=12;
int k,vis[1<<N];
int a[1<<N][1<<N];
int st[1<<N],top;
void dfs(int x){
vis[x]=1;
int v=(1<<k)-1;
int val=(x<<1)&v;
if(!vis[val]){
dfs(val);
st[++top]=0;
}
if(!vis[val|1]){
dfs(val|1);
st[++top]=1;
}
}
int main(){
scanf("%d",&k);
printf("%d ",(1<<k));
vis[0]=1;
dfs(0);
for(int i=1;i<=k;++i)st[++top]=0;
if(st[1]==0){
int pos=1;
while(st[pos]==0)st[pos]=-1,pos++;
}
while(top&&~st[top])printf("%d",st[top--]);
return 0;
}