1. 선형 기저(Linear Basis)의 정의와 성질

집합 $S$에 대한 XOR 선형 기저 $B$는 $S$의 부분집합 XOR 합으로 만들 수 있는 모든 값의 집합을 동일하게 생성할 수 있는 최소 크기의 집합입니다. 선형 대수학에서의 기저(Basis) 개념을 XOR 연산과 벡터 공간 $GF(2)^n$으로 가져온 것이라 이해할 수 있습니다.

선형 기저는 다음과 같은 핵심 성질을 가집니다.

• 원래 수열의 어떤 원소라도 기저 원소들의 XOR 합으로 표현 가능합니다.
• 기저 내의 어떤 원소들을 XOR 하더라도 0을 만들 수 없습니다(선형 독립).
• 성질을 유지하는 선에서 원소의 개수가 최소이며, 이 개수는 유일합니다.

2. 핵심 연산 구현

기저의 각 원소는 서로 다른 최고차 비트(MSB)를 가지도록 관리합니다. 이를 통해 가우스 소거법과 유사한 방식으로 연산을 수행할 수 있습니다.

2.1 원소 삽입 (Insertion)

가장 높은 비트부터 검사하며, 해당 비트 위치에 이미 기저 원소가 있다면 XOR 연산을 통해 값을 줄여나가고, 비어있다면 그 위치에 삽입합니다.

struct LinearBasis {
    long long basis[64];
    bool has_zero = false;

    LinearBasis() {
        memset(basis, 0, sizeof(basis));
    }

    void insert(long long val) {
        for (int i = 62; i >= 0; i--) {
            if (!(val >> i & 1)) continue;
            if (!basis[i]) {
                basis[i] = val;
                return;
            }
            val ^= basis[i];
        }
        has_zero = true;
    }
};

2.2 최댓값 및 최솟값 쿼리

최댓값은 그리디 알고리즘을 사용합니다. 현재 결과값에 기저 원소를 XOR 했을 때 값이 커진다면 업데이트합니다. 최솟값은 기저에서 가장 낮은 비트를 가진 원소입니다. 단, 0을 만들 수 있는 경우 0이 최솟값이 됩니다.

long long getMax() {
    long long res = 0;
    for (int i = 62; i >= 0; i--) {
        if ((res ^ basis[i]) > res) {
            res ^= basis[i];
        }
    }
    return res;
}

long long getMin() {
    if (has_zero) return 0;
    for (int i = 0; i <= 62; i++) {
        if (basis[i]) return basis[i];
    }
    return 0;
}

2.3 K번째 최솟값

K번째 값을 구하기 위해서는 기저를 재구성하여 각 기저 원소의 MSB 위치에 다른 원소들의 비트가 0이 되도록(Reduced Row Echelon Form) 만들어야 합니다.

vector<long long> refined;
void build() {
    refined.clear();
    for (int i = 0; i <= 62; i++) {
        for (int j = i - 1; j >= 0; j--) {
            if (basis[i] >> j & 1) basis[i] ^= basis[j];
        }
    }
    for (int i = 0; i <= 62; i++) {
        if (basis[i]) refined.push_back(basis[i]);
    }
}

long long queryKth(long long k) {
    if (has_zero) k--;
    if (k >= (1LL << refined.size())) return -1;
    long long res = 0;
    for (int i = 0; i < refined.size(); i++) {
        if (k >> i & 1) res ^= refined[i];
    }
    return res;
}

3. 오프라인 삭제가 가능한 선형 기저

단순한 선형 기저는 삭제 연산이 어렵습니다. 하지만 각 원소의 '유효 기간' 또는 '삭제 시점'을 알고 있다면, 그리디하게 기저를 유지하여 특정 시점의 최댓값을 구할 수 있습니다.

원소를 삽입할 때, 이미 기저에 있는 원소보다 현재 삽입하려는 원소의 삭제 시점이 더 늦다면 두 원소를 교체합니다. 더 오래 살아남는 원소를 상위 비트에 배치하여 기저의 효율성을 극대화하는 전략입니다.

struct DynamicBasis {
    long long basis[64];
    int survive_until[64];

    void insert(long long val, int time) {
        for (int i = 62; i >= 0; i--) {
            if (!(val >> i & 1)) continue;
            if (survive_until[i] < time) {
                swap(basis[i], val);
                swap(survive_until[i], time);
            }
            if (!val) return;
            val ^= basis[i];
        }
    }

    long long queryMax(int current_time) {
        long long res = 0;
        for (int i = 62; i >= 0; i--) {
            if (survive_until[i] >= current_time && (res ^ basis[i]) > res) {
                res ^= basis[i];
            }
        }
        return res;
    }
};

4. 응용 사례: 그래프에서의 XOR 경로

그래프에서 $1$번 노드에서 $N$번 노드로 가는 경로의 XOR 합을 최대화하는 문제는 선형 기저의 대표적인 응용입니다. 임의의 경로는 '임의의 단순 경로 + 사이클들의 XOR 합'으로 표현될 수 있습니다.

1. DFS를 통해 그래프를 탐색하며 모든 기초 사이클(Fundamental Cycles)을 찾아 그 XOR 합을 선형 기저에 삽입합니다.
2. $1$번에서 $N$번까지 가는 아무 단순 경로의 XOR 합을 초기값으로 설정합니다.
3. 기저를 이용해 해당 초기값에 대한 최댓값을 쿼리합니다.

void findCycles(int u, long long current_xor) {
    visited[u] = true;
    path_xor[u] = current_xor;
    for (auto& edge : adj[u]) {
        if (!visited[edge.to]) {
            findCycles(edge.to, current_xor ^ edge.weight);
        } else {
            basis.insert(current_xor ^ edge.weight ^ path_xor[edge.to]);
        }
    }
}

5. 확률과 기댓값에서의 활용

XOR 연산은 비트별로 독립적이기 때문에, 각 비트가 결과에 포함될 확률을 계산할 때 선형 기저가 유용하게 사용됩니다. 기저의 성질에 의해, 특정 비트가 1인 원소가 기저에 하나라도 존재한다면, 모든 가능한 부분집합 XOR 합 중 해당 비트가 1일 확률은 정확히 $1/2$이 됩니다.

이 성질을 이용하면 거듭제곱의 기댓값($E[X^k]$) 문제를 해결할 때, $k$가 작다면 비트 조합을 직접 계산하고 $k$가 크다면 선형 기저의 크기가 작다는 점($\log V$)을 이용하여 모든 가능한 XOR 합을 직접 탐색하는 방식을 취할 수 있습니다.