#P18325. Another Long Sequence Inversion

Another Long Sequence Inversion

Another Long Sequence Inversion

标准输入、标准输出。

给定三个以二进制表示的非负整数 L,R,XL,R,X,求长度为 R−L+1R-L+1 的整数序列

(L⊕X, (L+1)⊕X, …, R⊕X)(L\oplus X,\ (L+1)\oplus X,\ \ldots,\ R\oplus X)

的逆序对数,并以二进制输出。其中 ⊕\oplus 表示按位异或。

长度为 MM 的序列 B=(B1,…,BM)B=(B_1,\ldots,B_M) 的逆序对数,是满足 1≤i<j≤M1\le i<j\le M 且 Bi>BjB_i>B_j 的整数对 (i,j)(i,j) 的数量。

共有 TT 组测试数据,请分别求解。

输入格式

第一行一个整数 TT。接下来 TT 行,每行三个整数 L,R,XL,R,X,均用二进制表示。

输出格式

输出 TT 行。第 ii 行以二进制输出第 ii 组测试数据的逆序对数。

数据范围

  • 1≤T≤2×1051\le T\le 2\times10^5;
  • 0≤L≤R<2 2×1050\le L\le R<2^{\,2\times10^5};
  • 0≤X<2 2×1050\le X<2^{\,2\times10^5};
  • L,R,XL,R,X 的二进制表示均不含前导零;数 00 用单个字符 0 表示;
  • 所有测试数据中,RR 的二进制位数之和不超过 2×1052\times10^5;
  • 所有测试数据中,XX 的二进制位数之和不超过 2×1052\times10^5;
  • 所有输入值均为整数。

上述两个总位数限制分别计算。

样例输入 1

3
101 1000 10
1101 10111010 0
1000110 1110011011101 100011110010

样例输出 1

10
0
11100100001101111010100

样例说明

第一组测试数据中,L,R,XL,R,X 的十进制值分别为 5,8,25,8,2。异或后的序列为 (7,4,5,10)(7,4,5,10),逆序对有 (7,4)(7,4) 和 (7,5)(7,5),共 22 个,其二进制表示为 10。