CF2271C XOR Problem

给定一个整数 $n$。 定义数组 $a$ 的美丽度为 $|a| - f(a)$，其中 $|a|$ 是数组 $a$ 的长度，$f(a)$ 是数组 $a$ 所有按位异或为 $0$ 的非空子数组的数量。形式化地，$f(a)$ 是所有满足 $1 \le l \le r \le |a|$，且 $a_l \oplus a_{l + 1} \oplus \ldots \oplus a_r = 0$ 的 $(l, r)$ 对的数量。 在所有由 $0$ 到 $n$ 间的整数组成，并且美丽度最大的数组 $a$ 中，找到一个长度最大的数组。 注： $^\ast$ 若 $c$ 是从 $d$ 去掉若干（可能为零或全部）开头和结尾元素后得到的数组，则 $c$ 是 $d$ 的子数组。若两个子数组所删除元素的位置集合不同，则视为不同的子数组。 $^\dagger$ $\oplus$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$ 表示测试用例数量（$1 \le t \le 10^4$）。 接下来每组测试用例占一行，包含一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示数组元素的最大值。 保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

对于每个测试用例，输出一行一个整数 $k$ 表示数组的长度。 下一行输出 $k$ 个整数 $a_1, a_2, \ldots, a_k$（$0 \le a_i \le n$）表示数组的元素。 可以证明，在给定的限制下，所有测试用例的 $k$ 之和不超过 $10^6$。 如果有多种满足条件的数组，输出任意一种均可。

在第一个样例中，$n=1$，所以数组中的每个元素只能为 $0$ 或 $1$。一种可行的方案为 $a=[1, 1, 1]$，它恰好有两个异或为零的子数组，分别为 $(l, r)=(1,2)$ 和 $(l, r)=(2,3)$。这两个子数组元素相同，但位置不同，因此都计入，$a$ 的美丽度为 $3-2=1$。可以证明，任意一个长度为 $4$ 的、仅含 $0$ 和 $1$ 的数组，它的异或为零的子数组至少有 $4$ 个，因此美丽度至多为 $0$。 在第二个样例中，一种可行解为 $a=[2,2,1,0,2,0,1]$。其异或为零的子数组有 $(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$ 的数组能做到这一点。 由 ChatGPT 5 翻译