Найти число подмножеств, что исключающее оставшихся чисел равно 0

Question

Даны N чисел, найти минимальное число подмножеств, так что исключающее оставшихся чисел равно 0. Например:

{1,1,3,4,5}

результата является равным 3, потому что мы можем удалить подмножества {1,3} (двумя способами) или {3,4,5}.

Я ищу что-то более быстрое, чем O (2^n) грубая сила.

Это дубликат этого вопроса: Find number of subsets, that xor of remaining numbers equals to 0

Но ответ, который был отмечен ОР действительно неясно. Не могли бы вы переписать это? Или просто добавьте что-то самостоятельно.

Answer 1

Разрабатывая мой предыдущий answer:

Input: массив размера п, что 1 <= a[i] <= m

Выход: Количество подмножеств так, что исключающий из множества остальных чисел равно нуль. Обратите внимание на то, что это эквивалентно числу подмножеств, xor = X where X = xor of all elements of a

Рассмотрим ваш пример,

X = XOR({1,1,3,4,5}) = 2 Убедитесь, что XOR({1,3})=2 и XOR({3,4,5})=2

где XOR(set)== XOR of all elements of set

Решение:

Рассмотрите Dynamic Programming таблица размеров n * m.

D[i][j] = #subsets considering first i elements of a whose xor is j

Теперь для расчета таблицы, вам необходимо определить следующее рекуррентное соотношение:

D[i][j] = D[i-1][j] + D[i-1][j xor a[i]].

Интуиция/Proof:

Вы должны вычислить число подмножеств первых г элементов, исключающее является J. Фокус на Ith элемента а [I],

а [я] нет в подмножестве => любое подмножество i-1 элементов, исключающее это J будут действительны

а [I] присутствует в подмножестве => любое подмножество i-1 элементов, чей xor равно j xor a[i]. Это связано с тем, что когда мы добавляем к этому множеству [i], имеем j xor a[i] xor a[i] = j. Таким образом, xor нового набора j.

И, наконец, вы заполнили всю таблицу. Ваш ответ D[n][X], поскольку вам нужны те подмножества, xor которых X.

PS: Если вы все еще смущены, я предлагаю вам пройти технику динамического программирования. Попробуйте на своем примере, вы можете понять это лучше.