<BZOJ3033>太鼓达人

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
long long vis[2050],ans[2050],n,t;
int dfs(int x,int k)
{
    if(vis[x])return 0;
    if(k==t)return 1;
    vis[x]=1;ans[k]=x&1;
    if(dfs((x<<1)&(t-1),k+1))return 1;
    if(dfs((x<<1|1)&(t-1),k+1)) return 1;
    vis[x]=0;
    return 0;
}
int main()
{
    scanf("%lld",&n);
    t=1<<n;
    printf("%lld ",t);
    dfs(0,1);
    for(int i=1;i<=n-1;i++)printf("0");
    for(int i=1;i<=t-n+1;i++)printf("%lld",ans[i]);
    return 0;
}