对每一位独立考虑：该位上 $XOR$ 为该位被置 $1$ 的元素个数的奇偶性； $OR$ 为是否至少一个元素该位为 $1$ 。
要使 $XOR$ 与 $OR$ 在每一位都相等，必须“该位为 $1$ 的个数”要么为 $0$ ，要么为奇数（不能是正偶数）。
简单构造：
- $n$ 为奇数：输出全部为 $1$ 。此时最低位出现 $n$ 次（奇数），其他位为 $0$ 。
- $n$ 为偶数：输出 $n−1$ 个 $1$ ，最后一个为 $2$ 。此时最低位出现 $n−1$ 次（奇数），第二位出现 $1$ 次（奇数），其他位为 $0$ 。
值域均在 $1..1e9$ 内，复杂度 O( $∑n$ )。

P3370.第1题-构造异或数组

1000ms

Difficulty: 3

所属公司 : 饿了么

算法与标签>构造

题目内容

Tk 有一个长度为 $n$ 的数组 { $a_1,a_2,...,a_n$ } 初始数组中所有元素均为 $0$ 。Tk 希望你给数组的每个元素都赋予一个正整数，使得数组满足：

【按位异或】按位异或(xor)运算是对整数的二进制表示的每一位执行异或操作；

【按位或】按位或(or)运算是对整数的二进制表示的每一位执行或操作。

每个测试文件均包含多组测试教据。第一行输入一个整数 $T(1≦T≦10^4)$ 代表数据组数；

随后每组测试数据描述如下：

在一行上输入一个整数 $n(1≦n≦2×10^5)$ ；

除此之外，保证所有测试数据的 $n$ 之和不超过 $2×10^5$ 。

对于每一组测试数据，新起一行。输出 $n$ 个整数 $a_1,a_2,...,a_n(1≤a_i≤10^9)$ ，表示所构造的数组；可以证明一定有解。

如果存在多种可行解，可输出任意一种，系统会自动判定是否正确。

输入

2
4
1

输出

5 6 4 8
6

说明

对于第一组数据 $a_1$ $or$ $a_2$ $or...$ $or$ $a_n=15,$ $a_1$ $xor$ $a_2$ $xor...$ $a_n = 15$ 满足条件。

输入

预期输出（选填）