通常，人们习惯将所有 nn 位二进制串依照字典序排列，例如所有 22 位二进制串按字典序从小到大排列为：00，01，10，1100，01，10，11。

格雷码（Gray Code）是一种非凡的 nn 位二进制串排列法，它要求相邻的两个二进制串间恰好有一位不同，特地地，第一个串与最初一个串也算作相邻。

所有 2 位二进制串按格雷码排列的一个例子为：00，01，11，10。

n 位格雷码不止一种，上面给出其中一种格雷码的生成算法：

  1. 1 位格雷码由两个 1 位二进制串组成，程序为：0，10，1。
  2. n+1 位格雷码的前 2n 个二进制串，能够由依此算法生成的 n 位格雷码（总共 2n 个 n 位二进制串）按程序排列，再在每个串前加一个前缀 0 形成。
  3. n+1 位格雷码的后 2n 个二进制串，能够由依此算法生成的 n 位格雷码（总共 2n 个 n 位二进制串）按逆序排列，再在每个串前加一个前缀 1 形成。

综上，n+1 位格雷码，由 n 位格雷码的 2n 个二进制串按顺序排列再加前缀 0，和按逆序排列再加前缀 1 形成，共 2n+1 个二进制串。

另外，对于 n 位格雷码中的 2n 个二进制串，咱们按上述算法失去的排列程序将它们从 0 ∼ 2n−1 编号。

按该算法，2 位格雷码能够这样推出：

  1. 已知 11 位格雷码为 0，10，1。
  2. 前两个格雷码为 00，01。后两个格雷码为 11，10。合并失去 00，01，11，10编号顺次为 0 ∼ 3。

同理，3 位格雷码能够这样推出：

  1. 已知 2 位格雷码为：00，01，11，10。
  2. 前四个格雷码为：000，001，011，010。后四个格雷码为：110，111，101，100 110，111，101，100。合并失去：000，001，011，010，110，111，101，100，编号顺次为 0 ∼ 7。

当初给出 n,k，请你求出按上述算法生成的 nn 位格雷码中的 kk 号二进制串。

输出格局

仅一行，蕴含两个整数 nn 和 kk。

输入格局

仅一行，一个 nn 位二进制串示意答案。

数据范畴

对于 50% 的数据：n≤10
对于 80% 的数据：k≤5×106
对于 95% 的数据：k≤263−1
对于 100% 的数据：1≤n≤64,0≤k<2n

输出样例1：

2 3

输入样例1：

10

输出样例2：

3 5

输入样例2：

111

样例解释

对于样例1，2 位格雷码为：00，01，11，10，编号从 0 ∼ 3，因而 3 号串是 10。

对于样例2，3 位格雷码为：000，001，011，010，110，111，101，100，编号从 0 ∼ 7，因而 5 号串是 111。

思路：读题，n位格雷码能够由n-1位格雷码得出，所以咱们很容易的想到递归思路，一种思路是在每次递归时利用一个数据获取以后位数所有格雷码，而后最初返回一个数组，利用k当成下标而后返回后果。

当然这是第一工夫的想法，也的确能够通过肯定的测试样例，然而咱们留神到：对于 95% 的数据：k≤263−1k≤263−1。这样子咱们应用数组的想法也就告吹了，因为前面用来寄存的数据太多了，超过了最大值，所以pass。

这里咱们能够应用二分法解决这个问题，对于n=3，k=5的状况，咱们思考当k>=22时，这个时候也就是说k=5属于n的8个格雷码的后4个之一，这个时候最高位加上1,之后n=n-1=2,这里咱们留神到前四位格雷码的后两位是两头对称的。

也就是第三点：n+1 位格雷码的后 2n 个二进制串，能够由依此算法生成的 n 位格雷码（总共 2n 个 n 位二进制串）按逆序排列，再在每个串前加一个前缀 1 形成:

000，001，011，010，110，111，101，100000，001，011，010，110，111，101，100

好了咱们持续这个时候咱们失去第一位填1，n=2，k因为逆序所以是k = 8(23)-5(原k)-1= 2,因为k>=21,所以咱们接下来一位接着填1。

目前，咱们失去一个格雷码11_,此时n=1,并且k=4-2-1=1,此时咱们曾经到了完结条件(n=1,表明这是最初一位须要填入的),很显然这个时候咱们失去的k不是1就是0，咱们把k填入即可。

最初咱们对n=3,k=5的输出失去的格雷码为111,而111就是k=5对应的格雷码。

把下面的思路整顿成代码即可，咱们应用一个数组ans存储每一位的信息,并初始化为100的长度。

然而咱们写完当前，咱们还留神到:对于 100% 的数据：1≤n≤64,0≤k<2n1≤n≤64,java中最大的整数类型long的最大值是263-1，而k的最大值是264,很显著，咱们也不能间接应用Long这个类型获取k的值。

那么问题来了，如果想要齐全做出这道题，咱们仿佛连获取k的值都变得十分困难起来，有一个思路是利用char[]获取k的每一位,然而这里我没有尝试应用这种思路,我抉择应用Java的BigInteger来解决大数问题，那么这里咱们只须要将波及到k的解决改成BigInteger解决即可。

无关BigInteger的更多信息能够移步至上面的博客：
Java中BigInteger办法总结:https://www.jianshu.com/p/8b8...

好了，最初的代码如下：

import java.util.Scanner;import java.math.BigInteger;public class Main {    public static  int[] ans = new int[100];        public static void main(String[] args){        Scanner in = new Scanner(System.in);        String s = in.nextLine();        //获取输出        //留神1≤n≤64,0≤k<2n        int n = Integer.parseInt(s.split(" ")[0]);        BigInteger k = new BigInteger((s.split(" ")[1]));        //利用数组找下标的形式会超时        //必须思考到数字超过long的状况        //所以还是得用BigInteger进行大数解决        //应用二分法解题        dfs(n,k);        //应用数组存储后果        for(int i=n;i>=1;i--){            System.out.print(ans[i]);        }    }    public static void dfs(int pos, BigInteger k){        //边界条件        if(pos==1){            ans[pos] = k.intValue();            return;        }        BigInteger base  = BigInteger.valueOf(2);        BigInteger bwt = base.pow(pos-1);        //如果处于前半部分        if(k.subtract(bwt).longValue() < 0 ){            ans[pos] = 0;            dfs(pos-1, k);        }else{            //处于后半局部须要逆序            ans[pos] = 1;            dfs(pos-1, (base.pow(pos)).subtract(k.add(BigInteger.valueOf(1))));        }    }}