Поиск количества подмножеств с заданным Xor

Question

У меня есть массив с 10^5 элементами, где каждый элемент находится в [0, 1023]. Мне нужно найти число подмножеств массива, такое, что XOR элемента Q. (при Q> 1023 ответ равен 0). я пришел с этим O (N * 1024) подход

for (int i = 1; i <= n; i++) 
{ 
    int a = F[i]; 
    for (int j = 0; j < 1024; j++) 
    { 
     ways[i][j] = ways[i-1][j] + ways[i-1][j^a]; 
     if (ways[i][j] >= mod) 
      ways[i][j] -= mod; 
    } 
} 

Поскольку элементы находятся в диапазоне до 1023, может я сохранить массив Frequency F[i] , уменьшить выше код Шифрование до O (1024 * 1024) , Возможно ли, может ли использовать частотный массив?

Answer 1

Ну, ответ почти всегда 2^(N-10)

Во-первых, обратите внимание, что если вы XOR один элемент в другой, он не изменяет число подмножеств, XOR к Q.

Доказательство этого: Предположим, что у вас есть массив A размера N и множество подмножеств, которые XOR соответствуют определенным значениям. Тогда вы выполняете A [i]^= A [j], причем i! = J. Теперь, чтобы исправить все подмножества так, чтобы они были XOR одинаковыми значениями, вы просто найдете те, которые включают A [i], и переключите A [j] в них. Таким образом, XOR, который мы сделали, не влияет на общее количество подмножеств XOR на какое-либо конкретное значение.

Итак ...

1. Найти наибольший элемент и переместить его в положение 0. Тогда XOR его во все другие элементы, которые имеют тот же самый старший бит (самый старший бит), так что A [0 ] является единственным элементом с наибольшим MSB.

2. Найти самый большой оставшийся элемент, переместив его в положение 1 и XOR его во все остальные элементы с тем же MSB, поэтому A [1] будет единственным элементом со вторым по величине MSB.

3. Продолжайте работу с 3-м по величине MSB и т. Д. Столько раз, сколько сможете. В итоге вы получите не более 10 ненулевых элементов, все с разными MSB, а остальные элементы будут равны нулю.

Допустим, вы закончили с М ненулевыми элементами. Если вы можете сделать Q путем XORing этих элементов вместе, тогда будет только один способ сделать это. Остальные элементы N-M равны нулю, поэтому вы можете добавлять или удалять их из любого подмножества без изменения общего значения XOR. Итак, если вы можете сделать Q, тогда будут 2^(NM) подмножества, которые XOR - Q.

Если вы не можете сделать Q путем XORing ненулевых элементов, то, конечно, число подмножеств, которые XOR равно Q 0.

для получения дополнительной информации об этой процедуре, Google «Гаусса»