CF2271C.XOR Problem

普及/提高-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

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

题目描述

You are given an integer nn.

Define the beauty of an array aa as the value of ∣a∣−f(a)|a| - f(a), where ∣a∣|a| is the length of aa and f(a)f(a) is the number of non-empty subarrays∗^{\text{∗}} of aa with bitwise XOR equal to 00. Formally, f(a)f(a) is the number of pairs (l,r)(l, r) such that 1≤l≤r≤∣a∣1 \le l \le r \le |a| and al⊕al+1⊕…⊕ar=0a_l \oplus a_{l + 1} \oplus \ldots \oplus a_r = 0^{\text{†}}$.

Among all arrays aa consisting of integers from 00 to nn that have the maximum possible beauty, find one with maximum length.

∗^{\text{∗}}An array cc is a subarray of an array dd if cc can be obtained from dd by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. Two subarrays are considered different if the sets of positions of the deleted elements are different.

†^{\text{†}}\oplus$ denotes the bitwise XOR operation.

给你一个整数 nn。

定义数组 aa 的“优美值”为 ∣a∣−f(a)|a| - f(a),其中 ∣a∣|a| 表示数组 aa 的长度,而 f(a)f(a) 表示 aa 中异或值为 00 的非空子数组的个数。形式化地,f(a)f(a) 是满足 1≤l≤r≤∣a∣1 \le l \le r \le |a| 且 al⊕al+1⊕…⊕ar=0a_l \oplus a_{l + 1} \oplus \ldots \oplus a_r = 0 的所有数对 (l,r)(l, r) 的个数text†^{\\text{†}}。

在所有由 00 到 nn(含)之间的整数组成、且具有最大可能优美值的数组 aa 中,找出一个长度最大的数组。

∗^{\text{∗}} 若数组 cc 可通过对数组 dd 删除其开头若干(可能为零个或全部)元素及结尾若干(可能为零个或全部)元素得到,则称 cc 是 dd 的一个子数组。若两个子数组所删除的位置集合不同,则认为它们是不同的子数组。

†^{\text{†}} \oplus 表示 按位异或运算。

输入格式

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 only line of each test case contains a single integer nn (1≤n≤2⋅1051 \le n \le 2 \cdot 10^5) — the upper bound on the elements of the array.

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

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

每个测试用例仅有一行,包含一个整数 nn(1≤n≤2⋅1051 \le n \le 2 \cdot 10^5)——即数组元素的上界。

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

输出格式

For each test case, output a single integer kk — the length of the array. On the next line, output kk integers a1,a2,…,aka_1, a_2, \ldots, a_k (0≤ai≤n0 \le a_i \le n) — the elements of the array.

It can be shown that under the given constraints the sum of kk over all test cases does not exceed 10610^6.

If there are multiple suitable arrays, output any of them.

对于每个测试用例,输出一个整数 kk —— 数组的长度。在下一行,输出 kk 个整数 a1,a2,…,aka_1, a_2, \ldots, a_k(其中 0≤ai≤n0 \le a_i \le n)—— 数组的元素。

可以证明,在给定约束条件下,所有测试用例的 kk 值之和不超过 10610^6。

若存在多个满足条件的数组,输出其中任意一个即可。

输入输出样例

  • 输入#1

    2
    1
    2

    输出#1

    3
    1 1 1
    7
    2 2 1 0 2 0 1

说明/提示

In the first example, n=1n = 1, so every element of the array is equal to 00 or 11. One possible solution is a=[1,1,1]a = [1, 1, 1]: it has exactly two subarrays with bitwise XOR equal to 00, namely (l,r)=(1,2)(l, r) = (1, 2) and (l,r)=(2,3)(l, r) = (2, 3). These two subarrays consist of the same elements, but they occupy different positions, so both of them are counted, and the beauty of aa is 3−2=13 - 2 = 1. It can be proven that every array of length 44 with elements equal to 00 or 11 has at least four subarrays with bitwise XOR equal to 00, so its beauty is at most 00.

In the second example, one possible solution is a=[2,2,1,0,2,0,1]a = [2, 2, 1, 0, 2, 0, 1]. Its subarrays with bitwise XOR equal to 00 are (l,r)=(1,2)(l, r) = (1, 2), (2,7)(2, 7), (4,4)(4, 4), and (6,6)(6, 6), so the beauty of aa is 7−4=37 - 4 = 3. The array [1,2,2,1,2][1, 2, 2, 1, 2] has beauty 5−2=35 - 2 = 3 as well, but it is shorter. It can be shown that 33 is the maximum possible beauty for n=2n = 2, and that no array of length greater than 77 achieves it.

在第一个例子中,n=1n = 1,因此数组中的每个元素均为 00 或 11。一个可行的解是 a=[1,1,1]a = [1, 1, 1]:它恰好包含两个异或值(bitwise XOR)为 00 的子数组,即 (l,r)=(1,2)(l, r) = (1, 2) 和 (l,r)=(2,3)(l, r) = (2, 3)。这两个子数组虽然包含相同的元素,但占据不同位置,因此均被计入,故 aa 的优美度(beauty)为 3−2=13 - 2 = 1。可以证明,任意长度为 44、元素仅为 00 或 11 的数组至少包含四个异或值为 00 的子数组,因此其优美度至多为 00。

在第二个例子中,一个可行的解是 a=[2,2,1,0,2,0,1]a = [2, 2, 1, 0, 2, 0, 1]。其异或值为 00 的子数组为 (l,r)=(1,2)(l, r) = (1, 2)、(2,7)(2, 7)、(4,4)(4, 4) 和 (6,6)(6, 6),因此 aa 的优美度为 7−4=37 - 4 = 3。数组 [1,2,2,1,2][1, 2, 2, 1, 2] 的优美度同样为 5−2=35 - 2 = 3,但其长度更短。可以证明,当 n=2n = 2 时,最大可能的优美度为 33,且不存在长度超过 77 的数组能达到该优美度。

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

首页