题目描述
通常，人们习惯将所有 (n) 位二进制串按照字典序排列，例如所有 (2) 位二进制串按字典序从小到大排列为：(00,01,11,10)。
格雷码（(Gray Code)）是一种特殊的 (n) 位二进制串排列法，它要求相邻的两个二进制串间恰好有一位不同，特别地，第一个串与最后一个串也算作相邻。
所有 (2) 位二进制串按格雷码排列的一个例子为：(00)，(01)，(11)，(10)。
(n) 位格雷码不止一种，下面给出其中一种格雷码的生成算法：
- (1) 位格雷码由两个 (1) 位二进制串组成，顺序为：(0)，(1)。
- (n + 1) 位格雷码的前 (2^n) 个二进制串，可以由依此算法生成的 (n) 位格雷码（总共 (2^n) 个 (n) 位二进制串）按顺序排列，再在每个串前加一个前缀 (0) 构成。
- (n + 1) 位格雷码的后 (2^n) 个二进制串，可以由依此算法生成的 (n) 位格雷码（总共 (2^n) 个 (n) 位二进制串）按逆序排列，再在每个串前加一个前缀 (1) 构成。
综上，(n + 1) 位格雷码，由 (n) 位格雷码的 (2^n)个二进制串按顺序排列再加前缀 (0)，和按逆序排列再加前缀 (1) 构成，共 (2^{n+1}) 个二进制串。另外，对于 (n) 位格雷码中的 (2^n)个 二进制串，我们按上述算法得到的排列顺序将它们从 (0 sim 2^n - 1) 编号。
按该算法，(2)位格雷码可以这样推出：
- 已知 (1) 位格雷码为 (0)，(1)。
- 前两个格雷码为$ 00$，(01)。后两个格雷码为 (11)，(10)。合并得到 (00)，(01)，(11)，(10)，编号依次为 (0sim 3)。
同理，(3) 位格雷码可以这样推出：
- 已知 (2) 位格雷码为：(00)，(01)，(11)，(10)。
- 前四个格雷码为：(000)，(001)，(011)，(010)。后四个格雷码为：(110)，(111)，(101)，(100)。合并得到：(000)，(001)，(011)，(010)，(110)，(111)，(101)，(100)，编号依次为 (0sim7)。
现在给出 (n)，(k)，请你求出按上述算法生成的 (n) 位格雷码中的 (k) 号二进制串。
输入格式
仅一行两个整数 (n)，(k)，意义见题目描述。
输出格式
仅一行一个 (n) 位二进制串表示答案。
输入输出样例
输入 #1
2 3
输出 #1
10
输入 #2
3 5
输出 #2
111
输入 #3
44 1145141919810
输出 #3
00011000111111010000001001001000000001100011
说明/提示
【样例 (1) 解释】
(2) 位格雷码为：(00)，(01)，(11)，(10)，编号从 (0sim3)，因此 (3) 号串是 (10)。
【样例 (2) 解释】
(3) 位格雷码为：(000)，(001)，(011)，(010)，(110)，(111)，(101)，(100)，编号从 (0sim7)，因此 (5) 号串是 (111)。
【数据范围】
对于 (50\%) 的数据：(n leq 10)
对于 (80\%) 的数据：(k leq 5 imes 10^6)
对于 (95\%) 的数据：(k leq 2^{63} - 1)
对于 (100\%) 的数据：(1 leq n leq 64), (0 leq k lt 2^n)
这个题正解据说是位运算，但是似乎也不用这么麻烦。然而我考场上并没有开(unsigned) (long) (long)所以我就没了。
考虑按照题意模拟。按照题意，一个(n)位的格雷码是由一个前缀(0)或(1)加上一个长度为(n-1)为的格雷码构成的，所以我们可以考虑类似康托展开的方法。
我们不妨先处理出所有(2)的幂。对于我们知道这个长度为(n)的格雷码在当前所有长度为(n)的格雷码中应该正序排第(k)位，则如果(nlt 2^{n-1})（只有小于是因为编号是从(0)开始存的）则当前这一位还放(0)，转移到(dfs(n-1,k))；反之放下一个(1)，考虑怎么处理逆序。
由于我们已经放下了一个(1)，所以我们已经整个过滤掉了(2^{n-1})个比它排名靠前的格雷码（因为这些格雷码第一位应该是(0)），所以我们最后处理编号的范围是(2^{n-1})，所以我们首先要把(k)减掉(2^{n-1})。手玩一下可以知道，编号从(0)开始存这个事情非常麻烦，所以我们需要把这个数整个向右面移一位，也就是加上(1)。
再考虑要求倒序排列。这个很简单，因为这(2^{n-1})个格雷码的编号是(0sim2^{n-1}-1)，所以容易知道我们只需要用(2^{n-1}-(k-2^{n-1}+1))即可。（其实手玩一下或者打表找规律也行。）
上代码。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cmath>
#define int long long
#define rep(i,a,n) for(register int i=a;i<=n;++i)
#define dep(i,n,a) for(register int i=n;i>=a;--i)
using namespace std;
int n;
unsigned long long k;
unsigned long long num[64];
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
void write(int x)
{
if(x<0)putchar('-'),x=-x;
if(x==0)return;
write(x/10);
putchar(x%10+'0');
}
void dfs(int step,int k)
{
if(step==0)return;
if(k<num[step-1])
{
putchar('0');
dfs(step-1,k);
}
else
{
putchar('1');
dfs(step-1,num[step-1]-(k-num[step-1]+1));
}
}
signed main()
{
n=read(),k=read();
num[0]=1;
rep(i,1,n-1)num[i]=num[i-1]*2;
dfs(n,k);
return 0;
}
一定注意编号必须从(0)存，否则(unsigned) (long) (long)存不下。