题解 | #完美异或#

题目链接

完美异或

题目描述

给定一个整数 $n$ ，需要构造一个长度为 $n$ 的数组 $A = \{a_1, a_2, \dots, a_n\}$ ，该数组被称为“伟大数组”如果满足以下所有条件：

数组 $A$ 是单调非降的（ $a_1 \le a_2 \le \dots \le a_n$ ）。
所有元素 $a_i$ 都是非负整数。
数组的异或和 $X = a_1 \oplus a_2 \oplus \dots \oplus a_n$ 是 $n$ 的一个因子（即 $n \pmod X = 0$ ）。

如果存在这样的数组，输出任意一个；如果不存在，则输出 -1。

解题思路

这是一个构造性的问题。我们需要找到一种方法来构建一个满足所有三个条件的数组。

最棘手的条件是异或和 $X$ 必须是 $n$ 的因子。为了简化这个问题，我们可以尝试构造一个数组，使其异或和 $X$ 是一个特定的、容易满足整除条件的值。一个绝佳的选择是 $X=1$ ，因为 $1$ 是任何正整数 $n$ 的因子。

这样，问题就转化为：构造一个长度为 $n$ 的非降、非负整数数组，使其异或和为 $1$ 。

我们可以利用异或运算的性质 a \oplus a = 0 来抵消大部分元素，从而精确地控制最终的异或和。我们可以根据 $n$ 的奇偶性来分情况讨论：

情况一： $n$ 是奇数

设 $n = 2k+1$ 。我们可以让数组中大量的元素成对出现以使它们的异或和为 0。
我们构造 $n-1$ 个（一个偶数）相同的元素。例如，前 $n-1$ 个元素都设为 $0$ 。它们的异或和是 $0 \oplus 0 \oplus \dots \oplus 0 = 0$ 。
为了让整个数组的异或和为 $1$ ，我们只需要让最后一个元素 $a_n$ 满足 $0 \oplus a_n = 1$ ，所以 $a_n = 1$ 。
这样构造出的数组为 $A = \{0, 0, \dots, 0, 1\}$ （包含 $n-1$ 个 $0$ ）。
验证条件：
1. 非降： $0 \le \dots \le 0 \le 1$ ，满足。
2. 非负：所有元素都非负，满足。
3. 异或和： $X=1$ ， $1$ 是 $n$ 的因子，满足。
对于 $n=1$ 的特殊情况，此构造给出数组 $\{1\}$ ，异或和为 $1$ ， $1|1$ ，也满足。

情况二： $n$ 是偶数

设 $n = 2k$ 。我们不能像奇数情况那样只用一个不同的数，因为 $n-1$ 是奇数，无法简单地用相同元素抵消。
我们可以让前 $n-2$ 个元素（一个偶数）相同来抵消。同样，我们将它们设为 $0$ 。它们的异或和为 $0$ 。
现在我们需要设置最后两个元素 $a_{n-1}$ 和 $a_n$ ，使得它们的异或和为 $1$ (即 $a_{n-1} \oplus a_n = 1$ )，并且满足非降条件 ( $0 \le a_{n-1} \le a_n$ )。
有很多数对满足异或和为 $1$ ，例如 $(1,0), (2,3), (4,5)$ 等。
我们需要找到一对 $(b, c)$ 使得 $b \oplus c = 1$ 且 $0 \le b \le c$ 。
选择 $b=2, c=3$ 满足 $2 \oplus 3 = 1$ 和 $2 \le 3$ 。
这样构造出的数组为 $A = \{0, 0, \dots, 0, 2, 3\}$ （包含 $n-2$ 个 $0$ ）。
验证条件：
1. 非降： $0 \le \dots \le 0 \le 2 \le 3$ ，满足。
2. 非负：所有元素都非负，满足。
3. 异或和： $X=1$ ， $1$ 是 $n$ 的因子，满足。

综上所述，我们找到了一种对所有 $n \ge 1$ 都有效的构造方法，因此不存在无解的情况。

代码

c++
java
python

#include <iostream>

void solve() {
    int n;
    std::cin >> n;
    if (n % 2 != 0) { // n 是奇数
        for (int i = 0; i < n - 1; ++i) {
            std::cout << "0 ";
        }
        std::cout << "1\n";
    } else { // n 是偶数
        for (int i = 0; i < n - 2; ++i) {
            std::cout << "0 ";
        }
        std::cout << "2 3\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            if (n % 2 != 0) { // n 是奇数
                for (int i = 0; i < n - 1; i++) {
                    sb.append("0 ");
                }
                sb.append("1\n");
            } else { // n 是偶数
                for (int i = 0; i < n - 2; i++) {
                    sb.append("0 ");
                }
                sb.append("2 3\n");
            }
        }
        System.out.print(sb.toString());
    }
}

import sys

def solve():
    n_str = sys.stdin.readline()
    if not n_str:
        return
    n = int(n_str)
    
    if n % 2 != 0: # n 是奇数
        arr = ["0"] * (n - 1) + ["1"]
    else: # n 是偶数
        arr = ["0"] * (n - 2) + ["2", "3"]
    
    sys.stdout.write(" ".join(arr) + "\n")

def main():
    t_str = sys.stdin.readline()
    if not t_str:
        return
    t = int(t_str)
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

算法：构造法。根据 $n$ 的奇偶性，我们直接构造并输出一个满足条件的数组，其异或和恒为 $1$ 。
时间复杂度：对于每个测试用例，我们需要循环 $n$ 次来输出数组元素。由于所有测试用例的 $n$ 之和有上限，设为 $N_{total}$ ，则总时间复杂度为 $\mathcal{O}(N_{total})$ 。
空间复杂度：我们不需要存储整个数组，可以直接在循环中输出，因此只需要常数级别的额外空间，即 $\mathcal{O}(1)$ 。