算法

$O(n)$

规律：
用 s 表示 n 位数的一半（这样就不用特判最后一组）
当 k 大于一半的时候输出1， 并且要逆序
当 k 小于一半的时候输出0，不需要逆序
逆序实质就是倒过来数数，直接方法就是让s 乘以2 再减去k，
但是有超出long long 的风险，虽然侥幸AC， 但推荐改进：见代码
1ull 其实挺有用的，用1会错

C++ 代码

#include <iostream>
using namespace std;
typedef unsigned long long ull;
int main(){
    long long n, k, s;
    cin >> n >> k;
    s = 1ull << (n - 1);
    while(n--){
        if(k >= s){
            cout << 1;
            k = (s << 1) - k - 1;
        }
        else{
            cout << 0;
        }
        s >>= 1;
    }
    return 0;
}