CF2271C.XOR Problem
普及/提高-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given an integer n.
Define the beauty of an array a as the value of ∣a∣−f(a), where ∣a∣ is the length of a and f(a) is the number of non-empty subarrays∗ of a with bitwise XOR equal to 0. Formally, f(a) is the number of pairs (l,r) such that 1≤l≤r≤∣a∣ and al⊕al+1⊕…⊕ar=0^{\text{†}}$.
Among all arrays a consisting of integers from 0 to n that have the maximum possible beauty, find one with maximum length.
∗An array c is a subarray of an array d if c can be obtained from d 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.
†\oplus$ denotes the bitwise XOR operation.
给你一个整数 n。
定义数组 a 的“优美值”为 ∣a∣−f(a),其中 ∣a∣ 表示数组 a 的长度,而 f(a) 表示 a 中异或值为 0 的非空子数组的个数。形式化地,f(a) 是满足 1≤l≤r≤∣a∣ 且 al⊕al+1⊕…⊕ar=0 的所有数对 (l,r) 的个数text†。
在所有由 0 到 n(含)之间的整数组成、且具有最大可能优美值的数组 a 中,找出一个长度最大的数组。
∗ 若数组 c 可通过对数组 d 删除其开头若干(可能为零个或全部)元素及结尾若干(可能为零个或全部)元素得到,则称 c 是 d 的一个子数组。若两个子数组所删除的位置集合不同,则认为它们是不同的子数组。
† \oplus 表示 按位异或运算。
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤104). The description of the test cases follows.
The only line of each test case contains a single integer n (1≤n≤2⋅105) — the upper bound on the elements of the array.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.
每个测试包含多个测试用例。第一行包含测试用例的数量 t(1≤t≤104)。随后是各测试用例的描述。
每个测试用例仅有一行,包含一个整数 n(1≤n≤2⋅105)——即数组元素的上界。
保证所有测试用例中 n 的总和不超过 2⋅105。
输出格式
For each test case, output a single integer k — the length of the array. On the next line, output k integers a1,a2,…,ak (0≤ai≤n) — the elements of the array.
It can be shown that under the given constraints the sum of k over all test cases does not exceed 106.
If there are multiple suitable arrays, output any of them.
对于每个测试用例,输出一个整数 k —— 数组的长度。在下一行,输出 k 个整数 a1,a2,…,ak(其中 0≤ai≤n)—— 数组的元素。
可以证明,在给定约束条件下,所有测试用例的 k 值之和不超过 106。
若存在多个满足条件的数组,输出其中任意一个即可。
输入输出样例
输入#1
2 1 2
输出#1
3 1 1 1 7 2 2 1 0 2 0 1
说明/提示
In the first example, n=1, so every element of the array is equal to 0 or 1. One possible solution is a=[1,1,1]: it has exactly two subarrays with bitwise XOR equal to 0, namely (l,r)=(1,2) and (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 a is 3−2=1. It can be proven that every array of length 4 with elements equal to 0 or 1 has at least four subarrays with bitwise XOR equal to 0, so its beauty is at most 0.
In the second example, one possible solution is a=[2,2,1,0,2,0,1]. Its subarrays with bitwise XOR equal to 0 are (l,r)=(1,2), (2,7), (4,4), and (6,6), so the beauty of a is 7−4=3. The array [1,2,2,1,2] has beauty 5−2=3 as well, but it is shorter. It can be shown that 3 is the maximum possible beauty for n=2, and that no array of length greater than 7 achieves it.
在第一个例子中,n=1,因此数组中的每个元素均为 0 或 1。一个可行的解是 a=[1,1,1]:它恰好包含两个异或值(bitwise XOR)为 0 的子数组,即 (l,r)=(1,2) 和 (l,r)=(2,3)。这两个子数组虽然包含相同的元素,但占据不同位置,因此均被计入,故 a 的优美度(beauty)为 3−2=1。可以证明,任意长度为 4、元素仅为 0 或 1 的数组至少包含四个异或值为 0 的子数组,因此其优美度至多为 0。
在第二个例子中,一个可行的解是 a=[2,2,1,0,2,0,1]。其异或值为 0 的子数组为 (l,r)=(1,2)、(2,7)、(4,4) 和 (6,6),因此 a 的优美度为 7−4=3。数组 [1,2,2,1,2] 的优美度同样为 5−2=3,但其长度更短。可以证明,当 n=2 时,最大可能的优美度为 3,且不存在长度超过 7 的数组能达到该优美度。
输入解题思路,AI测评打分。不知道怎么写?