题目中给出了算法，所以我们只需要反着做就可以了。

对于给定的 \(n,k\) ，有两种情况。

• 编号为 \(k\) （编号为 \(k\) 不代表是第 \(k\) 个！题目中说编号是从 \(0\) 开始的！）的 \(n\) 位格雷码属于前 \(2^{n-1}\) 个，此时满足 \(k\lt 2^{n-1}\) 。
• 编号为 \(k\) 的 \(n\) 位格雷码后 \(2^{n-1}\) 个。

而前 \(2^{n-1}\) 个和后 \(2^{n-1}\) 又分别是由 \(n-1\) 位格雷码根据不同的规则转化而来的，所以我们很容易想到分治地递归求解。

基准情形是 \(n=1\) 的情况，直接返回 0 或 1 。

另外本题 \(n\lt 2^{64}\)，所以一定要开 unsigned long long 才（恰好）存的下。在计算的时候还要注意潜在的溢出可能性，比如说下面代码中的 (power[n-1]-k)+power[n-1]-1ull 如果先加两个 power[n-1] 的话对于 \(n=63\) 的情况直接溢出。

本题在判断时需要用到 \(2^x\) ，我选择了直接打表，毕竟其实表并不长，还更保险。打表程序比较简单，此处不放。

代码如下。

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

typedef long long Num;
typedef unsigned long long Unum;
typedef long double Lfloat;
#define Rint register int
#define It iterator
#define Os ostream
#define Is istream
#define Ifs ifstream
#define Ofs ofstream

#define AK_IOI bfw

template<typename T>
inline void read(T& num)
{
    char ch;int f;num=0;while(1){ch=getchar();if(ch=='-' || (ch>='0'&&ch<='9')) break;} (ch=='-')?(f=-1):(f=1,num+=ch-'0');while(1){ch=getchar();if(!(ch=='-' || (ch>='0'&&ch<='9'))) break; num*=10;num+=ch-'0';} num*=f;
}

Unum power[64]={/*表被和谐了 qwq*/};

string solve(int n,Unum k)
{
    if(n==1){return (k==0)?"0":"1";} //基准情况
    if(k<power[n-1]){return "0"+solve(n-1,k);}
    else{return "1"+solve(n-1,(power[n-1]-k)+power[n-1]-1ull);} //注意潜在的溢出漏洞！
}

int main()
{
    int n;
    Unum k;
    read(n); read(k);
    cout<<solve(n,k)<<endl;
    return 0;
}