算法1

(递归) $O(n^2)$（貌似）

注意unsigned long long，别炸了

C++ 代码

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>

using namespace std;

string solve(int n, unsigned long long k)
{
    if(n == 1)
        return k == 1 ? "1" : "0";

    if(k < ((unsigned long long)1 << (n - 1)) )
        return "0" + solve(n - 1, k);
    else
        return "1" + solve(n - 1, (unsigned long long)pow(2, n) - k - 1);
}

int main(void)
{
    int n;
    unsigned long long k;
    cin >> n >> k;

    cout << solve(n, k);

    return 0;
}

算法2

(最优解) $O(n)$

C++ 代码

#include<iostream>

using namespace std;

int main(void)
{
    int n;
    unsigned long long k;

    cin >> n >> k;

    k ^= k >> 1;

    while(~--n)
        cout << (k >> n & 1);

    return 0;

}