← 返回题目列表

Codeforces · 2071/D1

D1. 无限序列(简易版)

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

这是问题的简单版本。版本之间的区别在于,在这个版本中,$$$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$$$。

输出

对于每个测试用例,输出一个整数 - 给定范围内的元素之和。

示例

输入
复制

9
1 1 1
1
2 3 3
1 0
3 5 5
1 1 1
1 234 234
0
5 1111 1111
1 0 1 0 1
1 1000000000000000000 1000000000000000000
1
10 87 87
0 1 1 1 1 1 1 1 0 0
12 69 69
1 0 0 0 0 1 0 1 0 1 1 0
13 46 46
0 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.$$