思路

1. 分析核心条件

   问题的核心在于条件“$i \oplus a_i$ 的结果为奇数”。一个整数是奇数，当且仅当它的二进制表示的最低位为 $1$。

2. 异或运算与奇偶性

   我们来分析异或运算 $\oplus$ 对最低位的影响。两个数的异或结果的最低位，是这两个数最低位的异或结果。

   • 如果一个数 $x$ 是偶数，其二进制最低位是 $0$。
   • 如果一个数 $x$ 是奇数，其二进制最低位是 $1$。

   令 $LSB(x)$ 表示 $x$ 的最低位。条件 $i \oplus a_i$ 是奇数等价于 $LSB(i \oplus a_i) = 1$。 根据异或的性质，我们有 $LSB(i \oplus a_i) = LSB(i) \oplus LSB(a_i)$。 因此，条件转化为 $LSB(i) \oplus LSB(a_i) = 1$。

   这个等式成立的唯一可能是 $LSB(i)$ 和 $LSB(a_i)$ 不同，即一个为 $0$，另一个为 $1$。

3. 转化为奇偶配对问题

   • 如果 $i$ 是奇数（$LSB(i) = 1$），那么 $a_i$ 必须是偶数（$LSB(a_i) = 0$）。
   • 如果 $i$ 是偶数（$LSB(i) = 0$），那么 $a_i$ 必须是奇数（$LSB(a_i) = 1$）。

   简单来说，位置 $i$ 和它对应的元素 $a_i$ 的奇偶性必须相反。

4. 构造排列的可行性

   一个排列 $a$ 包含从 $1$ 到 $n$ 的所有整数，每个恰好一次。这意味着集合 $\{a_1, a_2, \ldots, a_n\}$ 和集合 $\{1, 2, \ldots, n\}$ 是完全相同的。

   我们需要将奇数位置映射到偶数值，并将偶数位置映射到奇数值。为了能成功建立这种一一映射（即排列），作为定义域和值域的集合大小必须相等。

   • 在 $\{1, 2, \ldots, n\}$ 中，奇数位置的数量必须等于偶数值的数量。
   • 在 $\{1, 2, \ldots, n\}$ 中，偶数位置的数量必须等于奇数值的数量。

   让我们来统计一下：

   • 奇数（位置或值）的数量为 $\lceil n/2 \rceil$。
   • 偶数（位置或值）的数量为 $\lfloor n/2 \rfloor$。

   因此，必须满足 $\lceil n/2 \rceil = \lfloor n/2 \rfloor$。这个等式当且仅当 $n$ 为偶数时成立。

   • 如果 $n$ 是奇数，比如 $n=3$，我们有 $\{1, 3\}$ 两个奇数和 $\{2\}$ 一个偶数。我们有两个奇数位置（$1, 3$）需要填入偶数，但我们只有一个偶数值（$2$），这是不可能的。
   • 因此，当 $n$ 为奇数时，不存在满足条件的排列，应输出 $-1$。

5. 构造具体解

   当 $n$ 为偶数时，奇数和偶数的数量相等，均为 $n/2$。因此解必定存在。我们可以给出一个简单的构造方法： 将相邻的数对 $(1, 2), (3, 4), \ldots, (n-1, n)$ 两两交换。

   即，对于 $i = 1, 3, 5, \ldots, n-1$，我们令：

   • $a_i = i + 1$
   • $a_{i+1} = i$

   我们来验证一下这个构造：

   • 对于奇数位置 $i$，我们填入 $a_i = i+1$，这是一个偶数。奇偶性相反，满足条件。
   • 对于偶数位置 $i+1$, 我们填入 $a_{i+1} = i$，这是一个奇数。奇偶性相反，满足条件。

   这个构造方法对于所有偶数 $n$ 都有效。例如，当 $n=4$ 时，排列为 $\{2, 1, 4, 3\}$。

C++

#include <iostream>
#include <vector>
#include <numeric>

// 提高IO效率
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

// 解决单个测试数据的函数
void solve() {
    int n;
    std::cin >> n;

    // 如果 n 是奇数，不存在满足条件的排列
    // 因为奇数位置和偶数值的数量不匹配（或反之）
    if (n % 2 != 0) {
        std::cout << -1 << "\n";
        return;
    }

    // 如果 n 是偶数，我们可以通过交换相邻的数来构造一个解
    // 例如，对于 n=4，构造 (2, 1, 4, 3)
    // 循环遍历 i = 1, 3, 5, ..., n-1
    for (int i = 1; i <= n; i += 2) {
        // 对于奇数位置 i，我们放置偶数 i+1
        // 对于偶数位置 i+1，我们放置奇数 i
        std::cout << i + 1 << " " << i << (i == n - 1 ? "" : " ");
    }
    std::cout << "\n";
}

int main() {
    fast_io();
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Python

import sys

def solve():
    """
    解决单个测试数据的函数
    """
    n = int(sys.stdin.readline())

    # 如果 n 是奇数，奇数和偶数的数量不相等，无法一一配对
    # 因此不存在满足条件的排列
    if n % 2 != 0:
        print(-1)
        return

    # 如果 n 是偶数，我们可以通过交换相邻数对 (i, i+1) 来构造
    # 结果是 [2, 1, 4, 3, ...]
    ans = []
    # 步长为2，遍历 i = 1, 3, 5, ...
    for i in range(1, n + 1, 2):
        # 将 (i+1, i) 添加到结果列表
        ans.append(i + 1)
        ans.append(i)
    
    # 将列表中的数字转换成字符串并用空格连接
    print(*ans)

def main():
    """
    主函数，处理多组测试数据
    """
    try:
        # 读取测试数据组数 T
        t = int(sys.stdin.readline())
        for _ in range(t):
            solve()
    except (IOError, ValueError):
        # 处理可能的输入结束或格式错误
        pass

if __name__ == "__main__":
    main()

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

    // 使用 Fast I/O 模板以提高读写效率
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }

    // 解决单个测试数据的函数
    private static void solve(FastReader sc, PrintWriter out) {
        int n = sc.nextInt();

        // 如果 n 是奇数，奇数位置和偶数值的数量（或反之）不匹配
        // 因此不存在满足条件的排列
        if (n % 2 != 0) {
            out.println(-1);
            return;
        }

        // 如果 n 是偶数，构造解：交换所有相邻数对 (1,2), (3,4), ...
        StringBuilder sb = new StringBuilder();
        // 循环遍历 i = 1, 3, 5, ..., n-1
        for (int i = 1; i <= n; i += 2) {
            // 对于奇数位置 i，我们放置偶数 i+1
            // 对于偶数位置 i+1，我们放置奇数 i
            sb.append(i + 1).append(" ").append(i);
            if (i < n - 1) {
                sb.append(" ");
            }
        }
        out.println(sb.toString());
    }

    public static void main(String[] args) {
        FastReader sc = new FastReader();
        PrintWriter out = new PrintWriter(System.out);
        
        // 读取测试数据组数 T
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc, out);
        }
        
        // 关闭输出流
        out.flush();
        out.close();
    }
}

题目内容

给定一个正整数 $n$ ，请你构造一个长度为 $n$ 的排列 {$a_1,a_2,...,a_n$}，满足：

• 对任意位置 $i$ (从 $1$ 开始)，$i⊕a_i$ 为奇数。

长度为 $n$ 的排列：由 $1,2,…,n$ 这 $n$ 个整数按任意顺序组成的数组(每个整数恰好出现一次)。例如， {$2,3,1,5,4$} 是一个长度为 $5$ 的排列；而 {$1,2,2$} 和 {$1,3,4$} 都不是排列。

这里的 $⊕$ 表示按位异或运算；奇数是指除以 $2$ 余数为 $1$ 的整数。

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数 $T(1 ≦T ≦2×10^5)$ 表示测试数据组数。此后 $T$ 行：

每行输入一个整数 $n(1≦n≦2×10^5)$ 。

除此之外，保证单个测试文件中所有 $n$ 的和不超过 $2 × 10^5$ 。

输出描述

对每组测试数据，新起一行输出：

• 若存在满足条件的排列，输出任意一个满足条件的排列，共 $n$ 个整数，数与数之间用一个空格隔开；

• 若不存在满足条件的排列，输出单个整数 $-1$ 。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

样例1

输入

2
1
2

输出

-1
2 1

说明

对于 $n=1$ ，无论 $a_1$ 取 $1$ ，均有 $1⊕1=0$ 为偶数，因此无解，输出 $-1$ 。

对于 $n=2$ ，取排列 {$2,1$} ：$1⊕2=3、2⊕1=3$，均为奇数，合法。