Thue-Morse Sequence

发布时间: 2018年8月14日 17:33   最后更新: 2018年8月14日 17:37   时间限制: 1000ms   内存限制: 256M

这是一个有趣的二进制序列。

$f_0=0$

$f_1=01$

$f_2=0110$

$f_3=01101001$

$f_4=0110100110010110$

严格地说,这个序列的第$n$项是由第$n-1$项与第$n-1$项按位取反后得到的序列拼接而成。

现在CSL拿到了这个序列的第$x$项,他想知道第$y$个字符是什么。(下标从$0$开始)

第一行是一个整数$T$,表示测试数据的组数。
接下来每一行表示一组测试数据,包含两个整数$x,y$。
$T \leq 10 ^ {5}$
$0 \le x, y \le 10 ^ {18}$

对于每组测试数据,在一行内输出$0$或$1$表示答案,如果不存在输出$-1$。

复制
5
4 0
4 1
4 2
4 3
4 4
0
1
1
0
1

math

ACM集训队暑期集训新生组队赛