CF2261G.1 2 3 and XOR, Where Did Everybody Go?

省选/NOI-

通过率:0%

时间限制:7.00s

内存限制:1024MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given a sequence aa consisting of nn non-negative integers.

Given a sequence bb consisting of kk non-negative integers, define a dot increment on bb as the following operation:

  • Select an index ii (1≤i≤k1 \le i \le k), and add any non-negative integer of choice to bib_i.

Then, let f(b)f(b) be the minimum value of b1⊕b2⊕…⊕bkb_1 \oplus b_2 \oplus \ldots \oplus b_k after performing a dot increment on bb exactly once.∗^{\text{∗}}

Please find the value of the following sum.

∑1≤l≤r≤nf([al,al+1,…,ar])\sum_{1 \le l \le r \le n}f([a_l,a_{l+1},\ldots,a_r])

∗^{\text{∗}}Here, ⊕\oplus denotes the bitwise XOR operation.

给你一个由 nn 个非负整数组成的序列 aa。

给定一个由 kk 个非负整数组成的序列 bb,定义对 bb 的**点增操作(dot increment)**为如下操作:

  • 选择一个下标 ii(1≤i≤k1 \le i \le k),并将任意选定的非负整数加到 bib_i 上。

然后,记 f(b)f(b) 为对 bb 恰好执行一次点增操作后,所能得到的 b1⊕b2⊕…⊕bkb_1 \oplus b_2 \oplus \ldots \oplus b_k 的最小值。∗^{\text{∗}}

请计算以下和式的值:

∑1≤l≤r≤nf([al,al+1,…,ar]) \sum_{1 \le l \le r \le n}f([a_l,a_{l+1},\ldots,a_r])

∗^{\text{∗}}此处 ⊕\oplus 表示按位异或运算(bitwise XOR)。

输入格式

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1041 \le t \le 10^4). The description of the test cases follows.

The first line of each test case contains an integer nn (1≤n≤4⋅1051 \le n \le 4\cdot 10^5).

The second line of each test case contains integers a1,a2,…,ana_1,a_2,\ldots,a_n (0≤ai<2250 \le a_i \lt 2^{25}).

It is guaranteed that the sum of nn does not exceed 4⋅1054\cdot 10^5 over all test cases.

每个测试包含多个测试用例。第一行包含测试用例的数量 tt(1≤t≤1041 \le t \le 10^4)。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 nn(1≤n≤4⋅1051 \le n \le 4\cdot 10^5)。

每个测试用例的第二行包含整数 a1,a2,…,ana_1,a_2,\ldots,a_n(0≤ai<2250 \le a_i \lt 2^{25})。

保证所有测试用例中 nn 的总和不超过 4⋅1054\cdot 10^5。

输出格式

For each test case, output the answer to the problem on a separate line.

对于每个测试用例,在单独的一行上输出该问题的答案。

输入输出样例

  • 输入#1

    4
    5
    5 4 6 7 5
    5
    3 3 2 2 3
    1
    67
    10
    1827481 5921082 14619611 643973 6718274 2948 244716 29 0 6717827

    输出#1

    43
    21
    67
    36695941

说明/提示

In the first test case, for example, consider f([5,4,6,7,5])f([5,4,6,7,5])

By incrementing b2=4b_2=4 by 11, bb becomes [5,5,6,7,5][5,5,6,7,5], and 5⊕5⊕6⊕7⊕5=45 \oplus 5 \oplus 6 \oplus 7 \oplus 5 = 4.

It can be shown that b1⊕b2⊕b3⊕b4⊕b5b_1 \oplus b_2 \oplus b_3 \oplus b_4 \oplus b_5 cannot be smaller than 44 after one dot increment.

The sum of minimum values over all subarrays can be shown to be 4343.

在第一个测试用例中,例如,考虑 f([5,4,6,7,5])f([5,4,6,7,5])。

通过将 b2=4b_2=4 增加 11,bb 变为 [5,5,6,7,5][5,5,6,7,5],此时 5⊕5⊕6⊕7⊕5=45 \oplus 5 \oplus 6 \oplus 7 \oplus 5 = 4。

可以证明:经过一次点增量操作后,b1⊕b2⊕b3⊕b4⊕b5b_1 \oplus b_2 \oplus b_3 \oplus b_4 \oplus b_5 的值不可能小于 44。

所有子数组的最小值之和可证为 4343。

输入解题思路,AI测评打分。不知道怎么写?

首页