给一个正整数 \(n\) ，找到一个序列 \(a_1, a_2, \cdots, a_n\) 满足
\[\bigoplus_{i=1}^{n} a_i = \frac{\sum_{i=1}^{n} a_i}{n}
\]
。
一个原始的问题： \(\bigoplus_{i=1}^{n}a_i=\sum_{i=1}^{n}a_i\) 。
- \(naive\) 的考虑 ：因为异或是“二进制中不进位的加法”，只需要让每个 \(a_i\) 的数位避开即可满足。容易想到 \(a_i = 2^{i - 1}\) 是一种构造。存在一个问题：数位不够多。最多可以用 \(int128\) 的 \(127\) 位。
- 若考虑不让数位避开的方式，则无解。因为 \(1 \oplus 1\) 只会减少异或的贡献。
为了扩展数位的选择，于是问题能扩展成 \(\bigoplus_{i=1}^{n}a_i=\frac{\sum_{i=1}^{n}a_i}{X}\) 。此时让某些位置上的 \(1\) 不避开可以减少异或贡献，构造这些位置可以让等式取等。
这种构造选取让 \(a_i\) 更可控，再逐渐调试的原则。
此题的一个思路是，为了让 \(a_i\) 更可控，不妨让所有 \(a_i = x\) ，不难发现 \(\frac{\sum_{i=1}^{n}a_i}{n}=x\) 。
- 当 \(n\) 为奇数，此时也有 \(\bigoplus_{i=1}^{n}a_i = x\) 。
- 当 \(n\) 为偶数，此时 \(\bigoplus_{i=1}^{n}a_i = 0\) 。此时不妨选 \(a_1, a_2\) ，有 \(a_1 + a_2 = 2x\) 且 \(a_1 \oplus a_2 = x\) 。
- 这又是一个经典问题：\(x \oplus y = \frac{x + y}{2}\) 。
- 最好的构造是 \(x=?011?,y=?001?\) ，此时 \(x+y=?100?, x \oplus y=?010?\) ，只要 \(?\) 的位置相等，既满足 \(x+y=(x \oplus y) << 1\) 。
- 于是 \(?\) 位置为若干个（可能是 \(0\) 个） \(0\) 。同时最小的 \(x, y\) 为二进制的 \(01, 11\) 即 \(1, 3\) 。
不妨一开始让 \(a_i = 2\)
- 若 \(n\) 为奇数，则满足条件。
- 若 \(n\) 为偶数，再让 \(a_1 = 1, a_2 = 3\) 。
view
#include <bits/stdc++.h>
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a ; }
void solve() {
int n; std::cin >> n;
std::vector<int> a(n, 2);
if (~n&1) a[0] = 1, a[1] = 3;
for (int i = 0; i < n; i++) std::cout << a[i] << " \n"[i==n-1];
}
signed main() {
int _ = 1; std::cin >> _;
while (_--) { solve(); }
return 0;
}