Линейный базис по XOR

Множество значений, которые можно получить как XOR подмножества данных чисел, — это линейная оболочка над полем из двух элементов. У неё есть базис, и он строится за $O(n \log C)$.

Построение

Держим массив, где basis[b] — вектор, старший единичный бит которого равен $b$.

void add(unsigned long long x) {
    for (int bit = 59; bit >= 0; bit--) {
        if (!(x >> bit & 1)) continue;
        if (!basis[bit]) { basis[bit] = x; return; }
        x ^= basis[bit];
    }
    // x обнулился: он выражается через уже добавленные
}

Это метод Гаусса: вместо вычитания строки — XOR, а делить не нужно вовсе, потому что коэффициенты бывают только нулём и единицей.

Что из него достаётся

вопрос	ответ
сколько различных значений достижимо	$2^r$, где $r$ — размер базиса
наибольшее достижимое	жадно по битам, см. ниже
выражается ли $x$	добавить $x$ в копию базиса: обнулился — да
$k$-е по возрастанию	привести базис к ступенчатому виду и взять биты $k$

Почему значений ровно $2^r$: разные подмножества базиса дают разные значения (иначе их XOR был бы нулевым, то есть базис зависим), а всего подмножеств $2^r$.

Наибольшее значение

unsigned long long best = 0;
for (int bit = 59; bit >= 0; bit--)
    if (basis[bit] && !(best >> bit & 1)) best ^= basis[bit];

Условие !(best >> bit & 1) существенно: элемент базиса добавляем только если он улучшает ответ. Иначе XOR обнулит уже установленный бит.

Жадность верна, потому что у каждого элемента базиса свой старший бит: добавление одного не портит старшие биты, поставленные раньше.

Где встречается

• «Сколько различных значений XOR подмножеств» — прямо размер оболочки;
• «Максимальный XOR подмножества» — жадность выше;
• «Максимальный XOR на отрезке массива» — базис с временными метками;
• задачи про линейную независимость векторов над $\mathbb{F}_2$ вообще.

Заметьте разницу с задачей «максимальный XOR пары»: там подмножество состоит ровно из двух элементов, и базис не помогает — нужен бор по битам.

Смежное

• Исключающее «или»;
• Маска как множество.