← 返回题目列表

AtCoder · arc213_b

B. 汉明距离不为 1

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

分数: 800 点

问题陈述

给你非负整数 q,L,R\;(q \in \{ 0,1\}, \; L \leq R)。 考虑一组 S 满足以下所有条件。

  • S 由不同的整数组成 L 和 R,包括在内。
  • If a \in S, \; b \in S, \; a \neq b,那么 a 和 b 的二进制表示形式至少有两位不同。 更正式地说,至少存在两个非负整数 i 这样 \left\lfloor\frac{a}{2^i}\right\rfloor 和 \left\lfloor\frac{b}{2^i}\right\rfloor 具有不同的奇偶校验。
  • 满足上述两个条件的元素中,元素数量最多。

If q=0,找到这样一个集合中的元素数量 S.
If q=1,构造一个这样的集合 S.

对于每个输入文件,求解 T 测试用例。

约束

  • 1 \leq T \leq 2 \times 10^5
  • 0 \leq q \leq 1
  • 0 \leq L \leq R \leq 10^{18}
  • 总和 q(R-L) 所有测试用例最多 5\times 10^6.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
case_1
case_2
\vdots
case_T

每个案例均按以下格式给出:

q L R

输出

总共输出答案 T 行。
的 t- 第行应包含以下问题的答案 t- 第一个测试用例。
对于每个测试用例,如果 q=0,打印集合中的元素数量 S 满足条件。
If q=1,一套 S 满足条件,令

B_i=\begin{cases} 1 \; (S \text{ contains } i) \\ 0 \; (S \text{ does not contain } i) \end{cases}

并按以下格式输出:

B_LB_{L+1}\dotsB_R

如果有多组 满足条件的 S ,可以打印任意一个。


示例输入 1

3
1 0 3
0 1 2
1 213 213

示例输出 1

1001
2
1

在第一个测试用例中, S=\{0,3\} 满足条件。 S=\{1,2\} 也满足条件,因此也是正确的。
在第二个测试用例中,唯一的 满足条件的 S 是 \{1,2\},其元素数量为 2.