logoChat01.ai

E. Adjacent XOR time limit per test2 seconds memor...

作成日: 2025年8月10日

使用モデル GPT-5 Thinking by Chat01

質問

E. Adjacent XOR
time limit per test2 seconds
memory limit per test256 megabytes

You're given an array a of length n. For each index i such that 1 \le i < n, you can perform the following operation at most once:

Assign a_i := a_i \oplus a_{i+1}, where \oplus denotes the bitwise XOR operation. .
You can choose indices and perform the operations in any sequential order.

Given another array b of length n, determine if it is possible to transform a to b.

Input
Each test contains multiple test cases. The first line contains the number of test cases t (1 \le t \le 10^4). The description of the test cases follows.

The first line of each test case contains one integer n (2 \le n \le 2 \cdot 10^5).

The second line of each test case contains n integers a_1, a_2, \dots, a_n (0 \le a_i < 2^{30}).

The third line of each test case contains n integers b_1, b_2, \dots, b_n (0 \le b_i < 2^{30}).

It is guaranteed that the sum of n over all test cases does not exceed 2 \cdot 10^5.

Output
For each test case, output "YES" (quotes excluded) if a can be transformed to b; otherwise, output "NO". You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Example
InputCopy
7
5
1 2 3 4 5
3 2 7 1 5
3
0 0 1
1 0 1
3
0 0 1
0 0 0
4
0 0 1 2
1 3 3 2
6
1 1 4 5 1 4
0 5 4 5 5 4
3
0 1 2
2 3 2
2
10 10
11 10
OutputCopy
YES
NO
NO
NO
YES
NO
NO
Note
In the first test case, you can perform the operations in the following order:

Choose index i=3 and assign a_3 := a_3 \oplus a_4 = 7, and a becomes [1, 2, 7, 4, 5].
Choose index i=4 and assign a_4 := a_4 \oplus a_5 = 1, and a becomes [1, 2, 7, 1, 5].
Choose index i=1 and assign a_1 := a_1 \oplus a_2 = 3, and a becomes [3, 2, 7, 1, 5].

give solution in cpp. there should be no comments in code

Python

python
import random, itertools

def reachable(a):
    n=len(a)
    res=set()
    # generate all subsets of indices 0..n-2 with at most once per index and all permutations
    indices=list(range(n-1))
    for k in range(n):
        pass
    # generate all subsets/permutations by BFS applying operations in any order using mask and sequence? We'll generate sequences of distinct indices of varying length without repetition
    # But that is huge; limit n small for test.
    def apply_seq(a, seq):
        arr=a[:]
        used=set()
        for i in seq:
            assert 0<=i<n-1 and i not in used
            used.add(i)
            arr[i]=arr[i]^arr[i+1]
        return tuple(arr)
    res=set([tuple(a)])
    # Use BFS to accumulate all unique arrays reachable where each index used at most once
    from collections import deque
    start=(tuple(a),0) # mask used
    seen=set([start])
    q=deque([start])
    while q:
        arr,mask=q.popleft()
        res.add(arr)
        for i in range(n-1):
            if not (mask>>i)&1:
                # we can apply op at i
                arr2=list(arr)
                arr2[i]=arr2[i]^arr2[i+1]
                mask2=mask | (1<<i)
                state=(tuple(arr2),mask2)
                if state not in seen:
                    seen.add(state)
                    q.append(state)
    return res

def condition(a, b):
    n=len(a)
    if b[-1]!=a[-1]:
        return False
    # process right to left checking if each b_i equals any of three options
    for i in range(n-2, -1, -1):
        ai=a[i]; ai1=a[i+1]; bi1=b[i+1]; bi=b[i]
        if not (bi==ai or bi==(ai^ai1) or bi==(ai^bi1)):
            return False
    return True

def test_many(trials=2000, maxn=6, maxval=8):
    for t in range(trials):
        n=random.randint(2,maxn)
        a=[random.randint(0,maxval-1) for _ in range(n)]
        R=reachable(a)
        # pick random b, test equivalence
        for _ in range(50):
            b=[random.randint(0,maxval-1) for _ in range(n)]
            cond=condition(a,b)
            possible=(tuple(b) in R)
            if cond!=possible:
                print("Mismatch!", a, b, cond, possible)
                return False
    print("All tests passed")
    return True

test_many(200, maxn=7, maxval=16)

True

思考

Implementing solution

The triple condition is verified using brute force for small cases. Now, for the C++ implementation: I'll read t test cases, check the condition efficiently, and loop through the array to verify the given relations for each test case. Logically, int is sufficient, but I'll use unsigned for safety while ensuring fast input/output. Time complexity is O(n).

Thought for 4m 8s

回答

cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    if(!(cin >> t)) return 0;
    while (t--) {
        int n;
        cin >> n;
        vector<unsigned int> a(n), b(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        for (int i = 0; i < n; ++i) cin >> b[i];
        bool ok = (a[n-1] == b[n-1]);
        for (int i = n - 2; i >= 0 && ok; --i) {
            unsigned int ai = a[i], ai1 = a[i+1], bi1 = b[i+1], bi = b[i];
            if (bi == ai || bi == (ai ^ ai1) || bi == (ai ^ bi1)) continue;
            ok = false;
        }
        cout << (ok ? "YES\n" : "NO\n");
    }
    return 0;
}

このQ&Aを共有