思路

题目要求我们验证对于任意一对下标 $i$ 和 $j$，等式 $a_i \oplus a_j = i \oplus j$ 是否恒成立。

如果我们直接遍历所有的下标对 $(i, j)$ 来进行检查，时间复杂度将是 $O(n^2)$。考虑到 $n$ 的最大值可以达到 $2 \times 10^6$，$O(n^2)$ 的算法显然会超时，因此我们需要寻找一个更高效的方法。

我们可以对给定的等式进行变形。按位异或运算有一个很好的性质：$x \oplus y = z \Leftrightarrow x \oplus z = y$。我们可以利用这个性质来简化条件。

将等式 $a_i \oplus a_j = i \oplus j$ 的两边同时异或上 $i$ 和 $j$： $(a_i \oplus a_j)$ $\oplus i \oplus j$ = ($i \oplus j$) $\oplus i \oplus j$ 由于任何数与自身异或的结果为0（$x \oplus x = 0$），并且任何数与0异或的结果是其本身（$x \oplus 0 = x$），所以右边变为0。 $a_i \oplus a_j \oplus i \oplus j = 0$ 利用异或运算的交换律和结合律，我们可以重新排列上式： $(a_i \oplus i) \oplus (a_j \oplus j) = 0$ 再次根据异或的性质，如果 $x \oplus y = 0$，那么必然有 $x = y$。因此，我们得到： $a_i \oplus i = a_j \oplus j$

这个变形后的等式是解题的关键。它告诉我们，原始条件“对于所有的 $i, j$ 都满足 $a_i \oplus a_j = i \oplus j$”等价于“对于所有的 $i, j$ 都满足 $a_i \oplus i = a_j \oplus j$”。

换句话说，对于数组中所有的元素，其值 $a_k$ 与其下标 $k$（注意是1-based下标）进行异或运算的结果都必须是一个相同的常量。

这样，问题就大大简化了。我们的算法可以是：

1. 任选一个下标，比如 $1$，计算出这个常量 $c = a_1 \oplus 1$。
2. 遍历数组中所有其他的下标 $i$（从 $2$ 到 $n$）。
3. 对于每一个 $i$，检查是否满足 $a_i \oplus i = c$。
4. 如果发现任何一个下标 $i$ 不满足这个条件，那么原始条件就不成立，我们就可以立即确定答案是 No。
5. 如果遍历完所有的下标都满足该条件，那么原始条件成立，答案是 Yes。

这个算法只需要遍历一次数组，时间复杂度为 $O(n)$，对于每个测试用例都能在规定时间内解决。在实现时，需要注意题目给的是1-based下标（$1, 2, ..., n$），而编程语言中的数组通常是0-based下标（$0, 1, ..., n-1$）。因此，对于数组中第 k 个位置的元素（0-based），其对应的题面下标是 k + 1。

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;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 如果只有一个元素，条件自然成立
    if (n <= 1) {
        std::cout << "Yes\n";
        return;
    }

    // 计算基准常量 c。
    // a[0] 对应 a_1，其下标为 1。
    int c = a[0] ^ 1;
    bool ok = true;

    // 从第二个元素开始检查
    // a[i] 对应 a_{i+1}，其下标为 i+1
    for (int i = 1; i < n; ++i) {
        if ((a[i] ^ (i + 1)) != c) {
            ok = false; // 一旦发现不匹配，标记为false并退出循环
            break;
        }
    }

    if (ok) {
        std::cout << "Yes\n";
    } else {
        std::cout << "No\n";
    }
}

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

Java

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

public class Main {

    // 使用 BufferedReader 和 StringTokenizer 来加速输入
    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());
        }
    }

    public static void solve() {
        FastReader sc = new FastReader();
        int t = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            int n = sc.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
            }

            // 如果只有一个元素，条件自然成立
            if (n <= 1) {
                sb.append("Yes\n");
                continue;
            }

            // 计算基准常量 c。
            // a[0] 对应 a_1，其下标为 1。
            int c = a[0] ^ 1;
            boolean ok = true;

            // 从第二个元素开始检查
            // a[i] 对应 a_{i+1}，其下标为 i+1
            for (int i = 1; i < n; i++) {
                if ((a[i] ^ (i + 1)) != c) {
                    ok = false; // 一旦发现不匹配，标记为false并退出循环
                    break;
                }
            }

            if (ok) {
                sb.append("Yes\n");
            } else {
                sb.append("No\n");
            }
        }
        System.out.print(sb.toString());
    }

    public static void main(String[] args) {
        solve();
    }
}

Python

import sys

# 使用 sys.stdin.readline 来加速输入
def fast_input():
    return sys.stdin.readline().strip()

def solve():
    try:
        n_str = fast_input()
        if not n_str: return
        n = int(n_str)
        a = list(map(int, fast_input().split()))

        # 如果只有一个元素，条件自然成立
        if n <= 1:
            print("Yes")
            return

        # 计算基准常量 c。
        # a[0] 对应 a_1，其下标为 1。
        c = a[0] ^ 1
        ok = True

        # 从第二个元素开始检查
        # a[i] 对应 a_{i+1}，其下标为 i+1
        for i in range(1, n):
            if (a[i] ^ (i + 1)) != c:
                ok = False # 一旦发现不匹配，标记为false并退出循环
                break
        
        if ok:
            print("Yes")
        else:
            print("No")

    except (IOError, ValueError):
        return

def main():
    try:
        t_str = fast_input()
        if not t_str: return
        t = int(t_str)
        for _ in range(t):
            solve()
    except (IOError, ValueError):
        return

if __name__ == "__main__":
    main()

题目内容

小红得到了一个长为$n$ 的数组$a_1,a_2，.,a_n$，他想知道是否对于所有的下标$i,j(1≦i,j≦n)$,都满足等式$a_{i} \oplus a_{j}=i \oplus j$成立.

按位异或($\oplus$):两个整数的二进制表示按位进行异或运算。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T(1≦T≤10^3)$代表数据组数，每组测试数据描述如下:

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

第二行输入$n$个正整数$a_1,a_2,..,a_n(1≦a_i≦10^9)$代表数组的元素。

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

输出描述

对于每一组测试数据，新启一行。如果符合要求，输出$Yes$,否则输出$No$

样例1

输入

2
5
7 4 5 2 3
1 1 4 5 1 4

输出

Yes
No