用给定的Xor找到子集的数量 [英] Finding the No. of Subset with a Given Xor

问题描述

我有一个包含10 ^ 5个元素的数组，其中每个元素都在[0,103]中。
我必须找到一个数组的子集数，使元素的XOR为Q.（对于Q> 1023，答案为0）。
我想出了这个 O（N * 1024）方法

  for（int i = 1; i <= n; i ++）
 {
 int a = F [i]; （j = 0; j< 1024; j ++）
 {
 way [i] [j] =方式[i-1] [j] +方式[i-1 ] [j ^ a]; 
 if（ways [i] [j]> = mod）
 ways [i] [j]  -  = mod; 
} 
} 
  

由于元素的范围高达1023，我可以维持一个数组频率F [i]，将上述代码减少到 O（1024 * 1024）。
这是可能的，频率阵列可能有用吗？

解决方案

嗯，答案几乎总是2 ^（N-10）

首先，请注意，如果您将一个元素转换为另一个元素，则不会将XOR的子集数量更改为Q。

证明：让我们说你有你的数组A的大小为N，一堆子集XOR到特定值。然后你做A [i] ^ = A [j]，i！= j。现在，要修复所有子集，以便它们对同一个值进行异或，您只需找到包含A [i]的子集，然后在其中切换A [j]。所以我们做的XOR并不会影响任何特定值XOR的子集总数。

所以...

1. 找到最大的元素并将其移动到位置0.然后将其转换为具有相同MSB（最高有效位）的所有其他元素，以便A [0 ]是唯一具有最大MSB的元素。




2. 找到最大的剩余元素，将其移动到位置1，并将其XOR转换为所有剩余的元素，同样的MSB，所以A [1]将是第二大MSB的唯一元素。




3. 继续第三大MSB等等时间可以。您最多可以得到最多10个非零元素，全部不同的MSB，其余的元素都将为零。

让我们说你最终得到M个非零元素。如果您可以通过将这些元素进行异或来将Q置于一起，那么只有一种方法可以实现。其他N-M元素都为零，因此您可以从任何子集中添加或删除它们，而无需更改总XOR值。所以如果你可以使Q，那么将有2 ^（NM）子集XOR到Q。

如果你不能通过异或这些非零元素，那么XOR到Q的子集当然是0。

有关此过程的更多信息，Google高斯消除

I have an array with 10^5 elements where each element is in [0, 1023]. I have to find the number of subsets of an array such that XOR of element is Q. (for Q>1023 the answer is 0). I came up with this O(N*1024) Approach

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;
    }
}

Since elements are in Range up to 1023 , could i maintain an array of Frequency F[i] , reduce the above code upto O(1024*1024). Is this possible ,can Frequency array could be useful ?

解决方案

Well, the answer is almost always 2^(N-10)

First, note that if you XOR one element into another, it doesn't change the number of subsets that XOR to Q.

Proof of that: Lets say that you have your array A of size N, and a bunch of subsets that XOR to particular values. Then you do A[i] ^= A[j], with i!=j. Now, to fix all the subsets so that they XOR to the same values, you just find the ones that include A[i], and toggle A[j] in them. So the XOR we did doesn't affect the total number of subsets that XOR to any particular value.

So...

1. Find the largest element and move it into position 0. Then XOR it into all the other elements that have the same MSB (most significant bit), so that A[0] is the only element with the largest MSB.

2. Find the largest remaining element, moving it to position 1, and XOR it into all the remaining elements with the same MSB, so A[1] will be the only element with the second-largest MSB.

3. Continue with the 3rd largest MSB, etc., as many times as you can. You end up with at most 10 non-zero elements, all with different MSBs, and the remaining elements will all be zero.

Lets say you end up with M non-zero elements. If you can make Q by XORing these elements together, then there will only be one way to do it. The other N-M elements are all zero, so you can add or remove them from any subset without changing the total XOR value. So if you can make Q then there will be 2^(N-M) subsets that XOR to Q.

If you can't make Q by XORing those non-zero elements, then of course the number of subsets that XOR to Q is 0.

For more information on this procedure, google "Gaussian Elimination"

这篇关于用给定的Xor找到子集的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！