← 返回题目列表

AtCoder · tupc2024_f

F. 另一个长序列反转

中文机器翻译题面 查看原题

配点 : 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 。
例如, 3 \oplus 5 = 6 (二进制表示法: 011 \oplus 101=110)。

制約

  • 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 。