[BOJ/C++] 백준 13504 - XOR 합

두 수 XOR 합과 유사한 문제이다. 숫자를 이진수로 변경하여 트라이에 넣어주고, 숫자 중 i번째까지 XOR한 값을 prefix에 저장해서 답을 구한다.

같은 수를 XOR 연산하면 항상 0이 된다. 따라서 S[i] = A[1] ~ A[i]를 XOR 연산한 결과라고 한다면, A[i] ~ A[j]까지 XOR 연산한 결과를 S[j] - S[i - 1] 이라고 할 수 있다. 따라서 수를 트라이에 넣으면서 연산을 누적해나가며 S[i]와 S[j]를 XOR한 값이 가장 큰 것으로 찾는 것으로 변형할 수 있다.

#include <iostream>
#include <vector>
using namespace std; 

struct Node {
    int children[2]; 
    bool valid; 
    Node() {
        children[0] = children[1] = -1; 
        valid = false;
    }
};

vector<Node> trie; 
int root; 

int init() {
    Node node; 
    trie.push_back(node); 
    return (int)trie.size() - 1; 
}

void add(int node, int x, int index) {
    if (index == -1) {
        trie[node].valid = true; 
        return; 
    }

    int c = (x >> index) & 1; // 숫자 x의 바이너리에서 index번째 값을 가져옴
    if (trie[node].children[c] == -1) {
        int next = init(); 
        trie[node].children[c] = next; 
    }
    add(trie[node].children[c], x, index - 1); 
}

void add(int x) {
    add(root, x, 31); 
}

int search(int node, int x, int index) {
    if (index == -1) return 0; 
    int c = (x >> index) & 1; 
    c = 1 - c;  // 찾을 대상은 현재 비트의 반대 비트
    if (trie[node].children[c] == -1)
        c = 1 - c; 
    if (trie[node].children[c] == -1) return 0; 

    int next = 0; 
    if (c == 1) next = 1 << index; 
    return next | search(trie[node].children[c], x, index - 1); 
}

int search(int x) {
    return search(root, x, 31); 
}

int main() {
    ios_base::sync_with_stdio(false); 
    cout.tie(NULL); cin.tie(NULL);

    int t; cin >> t; 
    while (t--) {
        trie.clear();
        root = init(); 

        int n; cin >> n; 
        int ret = 0; // XOR한 최대 값을 저장
        int prefix = 0; // i번째까지 XOR한 값
        add(0); // 부분 수열의 원소가 하나일 수도 있다. 0 XOR A를 하면 A가 그대로 나오기 때문에
        for (int i = 0; i < n; i++) {
            int x; cin >> x; 
            prefix ^= x;
            add(prefix); 
            int cand = (search(prefix) ^ prefix); 
            if (ret < cand) ret = cand; 
        }
        cout << ret << endl;
    }
    return 0; 
}

트라이에는 입력 받은 수를 그대로 저장하는 것이 아니라, XOR 값을 누적으로 계산한 prefix값을 넣는다. 그리고 현재 값 (prefix)과 현재 값과 XOR하여 가장 큰 값을 (search(prefix)) XOR하면 현재까지의 부분수열 중 XOR한 값이 가장 큰 값을 구할 수 있다.

 

이해를 돕기 위해 조금 더 자세히 설명해보겠다. 

 

결국에는 입력받는 수열의 누적을 XOR 에 계산하는 것이다.
트라이에 값을 삽입할 때마다 각각의 값과 XOR했을 때 최댓값이 부분수열 XOR의 최댓값이 된다.

S[i] 는 첫번째부터 i까지의 원소의 XOR 값을 저장한 배열이다.
S[i]와 S[j] 값을 이용해 부분 수열의 XOR 값을 구할 수 있다.
예를 들어, S[4] XOR S[2] = (A[1]^A[2]^A[3]^A[4]) ^ (A[1]^A[2])이다. 같은 수를 XOR 하게 되면 0이 된다. 0과 어떤 수를 XOR하면 어떤 수와 같다.
따라서 S[4] XOR S[2] = A[3]^A[4]이고(i = 3, j = 4), 이는 A[i]와 A[j] 사이의 모든 수를 XOR한 값은 S[j]와 S[i -1] 을 XOR한 결과와 같다.

search(prefix) : 현재 prefix에 대해 가능한 최대 XOR을 찾는다. 트라이 검색을 통해 현재 prefix와 최대한 반대가 되는 비트를 가지는, 이전에 저장한 prefix를 찾는다. 따라서 prefix는 S[j]이고, search(prefix)는 이전에 저장한 S[i - 1] 가 되는 것이다. 이를 XOR 함으로써 A[i] 부터 A[j] 까지의 부분수열의 XOR을 구할 수 있다.