力扣 779. 第K个语法符号

思路

0
01
0110
01101001
……

可以看出，每一层前半是上一层的复制，后半是上一层的求反

因此，若k在当前层的前半，就是上一层的值；若k在当前层的后半，就是上一层k-2**(n-1)/2的反值。

解法

def kthGrammar(n, k):
    if n == 1:
         return 0
    if k <= 1 << (n -2):
        return kthGrammar(n - 1, k)
    else:
        return kthGrammar(n - 1, k - (1 << (n - 2))) ^ 1