这是问题的简单版本。版本之间的区别在于,在这个版本中,$$$l=r$$$。只有解决了该问题的所有版本,您才能破解。
给定一个正整数 $$$n$$$ 和无限二进制序列 $$$a$$$ 的前 $$$n$$$ 项,其定义如下:
- 对于 $$$m \gt n$$$,$$$a_m = a_1 \oplus a_2 \oplus \ldots \oplus a_{\lfloor \frac{m}{2} \rfloor}$$$$$$^{\text{*}}$$$。
你的任务是计算给定范围 $$$[l, r]$$$ 中元素的总和:$$$a_l + a_{l + 1} + \ldots + a_r$$$。
$$$^{\text{*}}$$$$$$\oplus$$$ 表示按位异或运算。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$l$$$ 和 $$$r$$$ ($$$1 \le n \le 2 \cdot 10^5$$$、$$$1 \le l=r\le 10^{18}$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$\color{red}{a_i \in \{0, 1\}}$$$) - 序列 $$$a$$$ 的前 $$$n$$$ 项。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 给定范围内的元素之和。
示例
输入复制
91 1 112 3 31 03 5 51 1 11 234 23405 1111 11111 0 1 0 11 1000000000000000000 1000000000000000000110 87 870 1 1 1 1 1 1 1 0 012 69 691 0 0 0 0 1 0 1 0 1 1 013 46 460 1 0 1 1 1 1 1 1 0 1 1 1
输出复制
1 1 0 0 1 0 1 0 0
注意
在第一个测试用例中,序列 $$$a$$$ 等于 $$[\underline{\color{red}{1}}, 1, 1, 0, 0, 1, 1, 1, 1, 1, \ldots]$$,其中 $$$l = 1$$$,$$$r = 1$$$。 $$$[1, 1]$$$ 范围内的元素总和等于 $$a_1 = 1.$$
在第二个测试用例中,序列 $$$a$$$ 等于 $$[\color{red}{1}, \color{red}{0}, \underline{1}, 1, 1, 0, 0, 1, 1, 0, \ldots]$$,其中 $$$l = 3$$$,$$$r = 3$$$。 $$$[3, 3]$$$ 范围内的元素总和等于 $$a_3 = 1.$$