XOR線形基（Linear Basis）は、与えられた数値列 A = {a₁, a₂, ..., a_n} に対して、その要素のXOR演算によって生成可能なすべての値を表現できる、最小サイズの集合 B を指します。線形基を用いることで、XORに関する複雑なクエリを効率的に処理できます。

主な性質

• B の任意の要素を組み合わせたXOR和は0になりません。
• 集合 B のサイズは、最大値を V としたとき O(log V) 以下に抑えられます。

基本アルゴリズム

1. 値の挿入

新しい値 val を基底に追加するプロセスです。高位ビットから順にチェックし、対応する基底が空であればその位置に値を保持し、既に値が存在する場合はXORして次数を下げます。

void add(long long val) {
    for (int i = MAX_BIT; i >= 0; --i) {
        if (!(val & (1LL << i))) continue;
        if (!basis[i]) {
            basis[i] = val;
            return;
        }
        val ^= basis[i];
    }
}

2. 最大XOR値の算出

特定の初期値 val に対して、基底とのXORを繰り返して得られる最大値を求めます。高位ビットから貪欲にXORを行い、値が増加する場合のみ更新します。

long long query_max(long long current) {
    for (int i = MAX_BIT; i >= 0; --i) {
        current = std::max(current, current ^ basis[i]);
    }
    return current;
}

3. 第K番目に小さい値の算出

まず基底を「対角化（各基底の最高ビットがその基底のみに現れる状態）」します。その後、ビットごとの寄与を考慮して k 番目の値を復元します。

void prepare() {
    for (int i = MAX_BIT; i >= 0; --i) {
        for (int j = i - 1; j >= 0; --j) {
            if (basis[i] & (1LL << j)) basis[i] ^= basis[j];
        }
    }
    vec.clear();
    for (int i = 0; i <= MAX_BIT; ++i) {
        if (basis[i]) vec.push_back(basis[i]);
    }
}

long long query_kth(long long k) {
    if (k > (1LL << vec.size())) return -1;
    long long res = 0;
    for (size_t i = 0; i < vec.size(); ++i) {
        if (k & (1LL << i)) res ^= vec[i];
    }
    return res;
}

応用と知見

• マージ可能性： 二つの線形基は O(log² V) で統合可能です。セグメント木などで空間的な管理も行えます。
• 挿入不可の判定： 値を挿入しようとした際に val が 0 になる場合、その値は既存の基底によって既に表現可能（線形従属）であることを示します。
• グラフ上の最大XORパス： 任意の2点間のパスは、「任意の1つのパス」と「グラフ内のサイクル」のXOR和として表現できます。サイクルをすべて線形基に追加することで、最大XORパス問題を解くことが可能です。