完美异或
时间限制：1 秒 空间限制：256 MB
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！ 
题目描述
给定一个长度为
n
n
n 的数组
{
a
1
,
a
2
,
…
,
a
n
}
\\{a_1, a_2, \\dots, a_n\\}
{a1,a2,…,an}，如果满足以下两条性质，则称其为伟天数组：
⨁
i
=
1
n
a
i
\\bigoplus_{i=1}^{n} a_i
⨁i=1nai 是
n
n
n 的一个因子，即
n
m
o
d
(
⨁
i
=
1
n
a
i
)
=
0
n \\bmod \\left(\\bigoplus_{i=1}^{n} a_i\\right) = 0
nmod(⨁i=1nai)=0。
现在给定整数
n
n
n，请你构造一个长度为
n
n
n 的伟天数组，或者判断不存在这样的数组。
【名词解释】
- 按位异或：xor 表示按位异或运算，运算方法为对两个整数的对应二进制位进行比较：若两位相同则结果为
0
0
0，不同则结果为1
1
1。 - 异或和：
⨁
i
=
1
n
a
i
\\bigoplus_{i=1}^{n} a_i
⨁i=1nai 表示将所有a
i
a_i
ai 依次按位异或得到的结果。
输入描述
每个测试文件均包含多组测试数据。
第一行输入一个整数
T
(
1
≤
T
≤
10
4
)
T\\ (1 \\le T \\le 10^4)
T (1≤T≤104) 代表数据组数，每组测试数据描述如下：
在一行上输入一个整数
n
(
1
≤
n
≤
2
×
10
5
)
n\\ (1 \\le n \\le 2 \\times 10^5)
n (1≤n≤2×105) —— 需要构造的数组长度。
除此之外，保证单个测试文件的
n
n
n 之和不超过
2
×
10
5
2 \\times 10^5
2×105。
输出描述
对于每一组测试数据：
- 如果存在伟天数组，请在一行上按照非递减顺序输出
n
n
n 个整数a
1
,
a
2
,
…
,
a
n
(
0
≤
a
i
≤
10
18
)
a_1, a_2, \\dots, a_n\\ (0 \\le a_i \\le 10^{18})
a1,a2,…,an (0≤ai≤1018)； - 如果不存在伟天数组，直接输出一个整数
−
1
-1
−1。
如果存在多种可行答案，你可以输出任意一种即可，系统会自动判定是否正确。
示例 1
输入：
3
1
2
3
输出：
1
1 3
2 2 3
说明：
在这一组样例中：
-
n
=
1
n = 1
n=1 时，数组{
1
}
\\{1\\}
{1} 的异或和为1
1
1，显然1
∣
1
1 \\mid 1
1∣1； -
n
=
2
n = 2
n=2 时，数组{
1
,
3
}
\\{1, 3\\}
{1,3} 的异或和为1
⊕
3
=
2
1 \\oplus 3 = 2
1⊕3=2，并且2
∣
2
2 \\mid 2
2∣2； -
n
=
3
n = 3
n=3 时，数组{
2
,
2
,
3
}
\\{2, 2, 3\\}
{2,2,3} 的异或和为2
⊕
2
⊕
3
=
3
2 \\oplus 2 \\oplus 3 = 3
2⊕2⊕3=3，并且3
∣
3
3 \\mid 3
3∣3。
备注
本题已于下方时间节点更新，请注意题解时效性：
数据范围与提示
-
1
≤
T
≤
10
4
1 \\le T \\le 10^4
1≤T≤104 -
1
≤
n
≤
2
×
10
5
1 \\le n \\le 2 \\times 10^5
1≤n≤2×105，单个测试文件中所有n
n
n 之和不超过2
×
10
5
2 \\times 10^5
2×105 -
0
≤
a
i
≤
10
18
0 \\le a_i \\le 10^{18}
0≤ai≤1018，数组需单调非降 - 存在性结论（构造思路参考）：
-
n
n
n 为奇数时，可令前n
−
1
n – 1
n−1 个元素均为0
0
0（或相同偶数），最后放一个n
n
n，此时异或和为n
n
n，满足n
∣
n
n \\mid n
n∣n； -
n
n
n 为偶数时，可构造异或和为2
2
2（或n
n
n 的某个偶数因子）的序列，例如保持单调并把末尾设置成合适的值，使异或和整除n
n
n。
-
解题思路
本题是构造题，要求构造一个长度为
n
n
n 的非降非负整数数组，使得其异或和是
n
n
n 的因子。通过分析异或运算的性质，可以给出一个极其简单的通用构造，适用于所有
n
n
n。
1. 问题等价转化
- 需要数组满足：非降、非负整数、异或和整除
n
n
n。 - 异或运算的性质：
0
0
0 是异或运算的单位元，即0
⊕
x
=
x
0 \\oplus x = x
0⊕x=x；任意多个0
0
0 异或结果仍为0
0
0。 - 目标：使异或和等于
n
n
n，由于n
m
o
d
n
=
0
n \\bmod n = 0
nmodn=0，这样n
n
n 必然是异或和的倍数（即异或和是n
n
n 的因子）。
2. 构造方法
- 对于任意
n
≥
1
n \\ge 1
n≥1，构造数组：前n
−
1
n-1
n−1 个元素全部为0
0
0，最后一个元素为n
n
n。 - 即数组为 [0, 0, …, 0, n]（共
n
n
n 个元素）。 - 验证：
- 非降：
0
≤
0
≤
⋯
≤
0
≤
n
0 \\le 0 \\le \\dots \\le 0 \\le n
0≤0≤⋯≤0≤n，显然成立。 - 非负整数：所有元素均
≥
0
\\ge 0
≥0，成立。 - 异或和：
0
⊕
0
⊕
⋯
⊕
0
⊕
n
=
n
0 \\oplus 0 \\oplus \\dots \\oplus 0 \\oplus n = n
0⊕0⊕⋯⊕0⊕n=n。 - 整除条件：
n
m
o
d
n
=
0
n \\bmod n = 0
nmodn=0，即异或和n
n
n 是n
n
n 的因子，满足要求。
- 非降：
- 因此，对于所有
n
n
n，该构造都合法，无需输出−
1
-1
−1。
3. 复杂度分析
- 时间复杂度：每组数据需要输出
n
n
n 个数字，所有测试数据的n
n
n 之和不超过2
×
10
5
2 \\times 10^5
2×105，总输出量很小，可以轻松通过。 - 空间复杂度：
O
(
1
)
O(1)
O(1)，仅使用常数个变量。
总结
利用
0
0
0 在异或运算中的中性性质以及
n
n
n 自整除的特点，构造极其简单。该构造对所有
n
n
n 均有效，避免了复杂的分类讨论。
代码简要说明
- 读入测试组数
T
T
T。 - 对于每组数据，读入
n
n
n，循环输出n
−
1
n-1
n−1 个 "0 "，最后输出n
n
n 并换行。 - 使用 ios::sync_with_stdio(0) 和 cin.tie(0) 加速输入输出。
代码内容
#include <bits/stdc++.h>
using namespace std;
#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1e3+10;
const ll INF=1e18;
const ll M=1e6+10;
const ll mod=1e9+7;
ll T,n;
void solve()
{
cin>>n;
for(ll i=1;i<=n–1;i++) cout<<"0 ";
cout<<n<<'\\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>T;
while(T—) solve();
return 0;
}
