分数: 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.