格雷码 题解

按题意模拟即可。可以使用左移快速计算出 $2^k$ 的结果。
注意 long long 的范围是 $[-2^{63},2^{63}-1]$，unsigned long long 的范围是 $[0,2^{64}-1]$，$2^{64}$ 他们两个都存不下，需要特判！

#include <iostream>
#include <cstdio>
#include <climits>
#define int unsigned long long 
using namespace std;
string dfs(int n, int m){
	if(n == 1) return to_string(m);
	if(m < (1ull << n - 1)) return "0" + dfs(n - 1, m);
	if(n == 64) return "1" + dfs(n - 1, ULLONG_MAX - m);
	return "1" + dfs(n - 1, (1ull << n) - m - 1);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m;
	cin >> n >> m;
	cout << dfs(n, m);

	return 0;
}

时间复杂度：$O(n)$。