$O(n)$

将格雷码的构造分成上下两个部分来构造

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
string f(ULL n,ULL k)
{
	if(n==0) return "";
	if(k<(1ull<<(n-1))) return "0"+f(n-1,k); //需要在前面补0
	else
	{
		ULL t=(1ull<<n)-1;
		if(n==64) t=-1;//无符号的最大值
		return "1"+f(n-1,t-k);  //需要在前面补1,然后逆序
	}
} 
int main() {
  	ULL n,k;
  	cin>>n>>k;
  	cout<<f(n,k);
    return 0;
}