配点 : 100 点
問題文
非負整数 L,R,X 以二进制给出。长度 R-L+1 整数序列 给出 (L \oplus X,(L+1)\oplus X, \dots, R\oplus X) 求长度为 的倒置数的二进制表示。
但是, 运算前设定中包含的\oplus 表示按位异或。
T 个测试用例,请分别求出答案。 包含在
倒置数是
数列 B=(B_1,B_2,\dots, B_M) 的倒置数是满足整数对 1 \leq i \lt j \leq M 找出可被 B_i \gt B_j 的个数。什么是按位异或?
非負整数 A,B 的按位异或 (XOR) A \oplus B 定义如下。 当- A \oplus B 以二进制表示法 2^k \, (k \geq 0) 中的位数为A,B 以二进制表示法 2^k 数字中只有一位是 1 如果 1,否则 输出为 0 。
制約
- 1 \leq T \leq 2 \times 10^5
- 0 \leq L \leq R \lt 2^{2 \times 10^5}
- 0 \leq X \lt 2^{2 \times 10^5}
- 所有输入均为整数
- T 是以十进制给出
- L,R,X 是以二进制给出,并且开头不包含多余的
0(但是视为 0 是 您也可以写 1 位的整数) - 1 个输入文件中 R 的二进制位数总和是 输出第 2 \times 10^5 以下
- 1 个输入文件中 X 的二进制位数总和是 输出第 2 \times 10^5 以下
部分点
附加限制 如果正确答案是满足 T \leq 3000, R \lt 2^{30}, X \lt 2^{30} 的数据集 给出 10 点。 如果您正确回答了所有满足
入力
输入是按以下格式从标准输入给出的。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出。 打印
L R X
出力
T 行。i 在线 i 个测试用例的答案。
入力例 1
3 101 1000 10 1101 10111010 0 1000110 1110011011101 100011110010
出力例 1
10 0 11100100001101111010100
1 关于第二个测试用例,L,R,X 分别以十进制表示时 L=5,R=8,X=2 。(5\oplus 2, 6\oplus 2, 7\oplus 2, 8\oplus 2)=(7,4,5,10) 因此应求的翻转数是 2 。