只解不答

只解不答，不放代码，仅提供思路参考，可放心查看。

先说说评价，这题目好，有难度，就是样例3的输入太臭了

看题目有给数据范围，分很多层，想要拿满分的第一关：

对于95%的数据，k≤2^63-1
对于100%的数据，0<k<2^n，1≤n≤64

2^63-1刚好是long long类型的数据范围，但会WA一个测试点，再一瞅k里头没负数，一眼看出请unsigned：

unsigned long long k;

接下来分析思路，题目标签里面给了递归就按照递归写，递归函数参数至少需要俩，一个是当前位数，一个是在该位数下与当前位单位的0或1组合的位数-1位的格雷码编号，而递归边界给出了1位的格雷码0，1。

由于格雷码是二进制数，用字符数组、字符串一类的类型还是比较好的。

string grey_code(int d,unsigned long long nowK); //d为当前位数，nowK为在当前位数格雷码下的格雷码编号

========重难点来了========

格雷码之所以可以使用递归，是因为它可以由固定规律的更少一位的格雷码与0或1以固定方式组合。

所以至少有

return "0"+grey_code(d-1,...);

这种写法。

而难点在于这个固定规律中的“逆序”。

要分析这个“逆序”的规律，首先得分析“顺序”。以3位格雷码中的编号1格雷码为例。

//二位格雷码 00 01 11 10
grey_code(3,1) = "0"+grey_code(2,1) = "0" + "01"

递归的时候，因为编号1的格雷码在3位格雷码中的前2^2=4位，所以是编号为1的2位格雷码加前缀0。

以3位格雷码中的编号5格雷码做对比：

//二位格雷码 00 01 11 10
grey_code(3,5) = "1"+grey_code(2,2) = "1" + "11"

可以看到，因为编号5的格雷码在3位格雷码中的后2^2=4位，所以是编号为1的逆序2位格雷码加前缀1。

注意，前后组合的降1位格雷码的编号并没有变，变的是排序方式。而观察逆序状态下对应编号的格雷码，会发现它等同于顺序状态下的 格雷码最大编号-原编号 编号的格雷码。

得到了逆序格雷码编号与顺序格雷码编号的转换方法，就可以写出顺序和逆序状态下的两种递归返回：

return "0"+grey_code(d-1,nowK); //顺序状态下，nowK，既格雷码编号，在降1位格雷码中不变
return "1"+grey_code(d-1,pow(2,d-1)-1-(nowK-pow(2,d-1))); 
//逆序状态下，nowK，既格雷码编号，在降1位格雷码中为 (nowK-降1位格雷码数量)
//又因为要转换为顺序状态下的格雷码编号，又要使用降1位格雷码最大编号来减去逆序状态下的编号
//拆开化简可以得到以下语句
return "1"+grey_code(d-1,2*pow(2,d-1)-1-nowK); 

自此，格雷码的重难点已经拆解完毕，相信你已经有了思路。

========结语========

怎么说呢，这题不算太难（我水平不高做得比较久），但是思路很有意思，
没有在题解区见到题解是令我感到奇怪的一件事。

想了想就自己写一篇算了，当作回顾思考总结。

end