Количество подмножеств, в которых XOR содержит менее двух установленных бит

Question

У меня есть массив A (размер <= 10 ^ 5) чисел (<= 10 ^ 8), и мне нужно ответить на некоторые запросы (50000), для L, R, сколько подмножеств для элементов в диапазоне [L, R], XOR подмножества - это число, для которого установлен 0 или 1 бит (степень 2). Кроме того, точечные изменения в массиве выполняются между запросами, поэтому на самом деле невозможно выполнить какую-либо автономную обработку или использовать такие методы, как квадратное root разложение и c. </p>

У меня есть подход, в котором я использую DP для вычисления для заданного диапазона, что-то вроде этого: https://www.geeksforgeeks.org/count-number-of-subsets-having-a-particular-xor-value/

Но это явно слишком медленно. Это похоже на классическую проблему дерева сегментов, но, похоже, не могу найти, какие точки данных хранить на каждом узле, так что я могу использовать левый и правый дочерние элементы для вычисления ответа для данного диапазона.

Answer 1

Да, DP не будет достаточно быстрым.

То, что будет достаточно быстрым, - это применение некоторой линейной алгебры над GF (2), полем Галуа с двумя элементами. Каждое число можно интерпретировать как битовый вектор; сложение / вычитание векторов - это XOR; Скалярное умножение на самом деле не имеет значения.

Данные, которые вам нужны для каждого сегмента, (1) сколько чисел существует в сегменте (2) основа для подпространства чисел, сгенерированных числами в сегменте, который будет состоять максимум из 27 чисел, потому что все числа меньше 2 ^ 27. Основой для одноэлементного сегмента является только это число, если оно ненулевое, иначе пустое множество. Чтобы найти интервал объединения двух базисов, используйте исключение Гаусса и отбросьте нулевые векторы.

Учитывая длину интервала и базис для него, вы можете посчитать количество хороших подмножеств с помощью ранга теорема недействительности. В основном, для каждого целевого числа используйте вашу процедуру исключения Гаусса, чтобы проверить, принадлежит ли целевой номер подпространству. Если так, то есть 2 ^ (длина интервала минус размер базиса) подмножества. Если нет, ответ ноль.