JZOJ 3383. 【NOIP2013模拟】太鼓达人

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#define N 2100
using namespace std;
int k, ans, a[N], t;
bool b[N];

bool dfs(int x, int dep)
{
    if (b[x])    return 0;
    if (dep == t)    return 1;
    b[x] = 1;
    a[dep] = x & 1;
    if (dfs((x << 1) & (t - 1), dep + 1))    return 1;
    if (dfs((x << 1 | 1) & (t - 1), dep + 1))    return 1;
    b[x] = 0;
    return 0;
}

int main()
{
    scanf("%d", &k);
    t = pow(2, k);
     printf("%d ", t);
    for (int i = 1; i <= k - 1; i++)
        printf("0");
    dfs(0, 1);
    for (int i = 1; i <= t - k + 1; i++)
        printf("%d", a[i]);
}