给定长度n的阵列，找到子集的数目，其中一个子集的异或等于给定数量的 [英] Given an array of length n, find number of subsets where XOR of a subset is equal to a given number

问题描述

给定一个数组

，改编，长度 N ，找到多少的子集ARR 有这样 XOR（^）的子集是等于给定的数字，答。

我有这样的 DP 的方法，但有改善其时间复杂度的一种方式。 答总是小于1024。

下面答是否定的。这样 XOR（^）子集等于它。
改编[N] 包含了所有的数字

  memset的（DP，0，sizeof的（DP））;
DP [0] [0] = 1;对于（i = 1; I＆LT; = N;我++）{
    为（J = 0; J＆LT; 1024; J ++）{
        DP [I] [j]的=（DP [I-1] [j]的+ DP [I-1] [J ^改编由[i]]）;
    }
}COUT＆LT;＆LT; （DP [N] [答]）;
 

解决方案

从<一个href=\"http://stackoverflow.com/questions/34148742/given-an-array-of-length-n-find-number-of-subsets-where-xor-of-a-subset-is-equa#comment56047309_34148742\">user3386109's发表评论，建立在你的code的顶部：

  / *警告：未经测试* /
INT计[1024] = {0}，方法[1024];
的for（int i = 1; I＆LT; = N; ++ i）统计[ARR [I] + = 1;
的for（int i = 0; I＆LT; = 1024; ++ I）{
  const int的Z =计数[I]
  //寻找溢出这里
  方式由[i] = Z == 0？
              0：
              （INT）（1U＆所述;≤（Z-1））;
}memset的（DP，0，sizeof的（DP））;
DP [0] [0] = 1;对于（i = 1; I＆LT; = 1024;我++）{
    为（J = 0; J＆LT; 1024; J ++）{
        //检查溢出
        const int的的howmany =方式[I] * DP [I-1] [J]。
        DP [I] [J] + =的howmany;
        DP [I] [J ^ I] + =的howmany;
    }
}COUT＆LT;＆LT; （DP [1024] [ANS]）;
 

有关计算奇_ 和 _甚至，也可以使用以下命令：

  

^N C ₀ + ^N C ₂ + ... =
   ^N C ₁ + ^N C ₃ ... =
  2 ^N-1

由于的方式来选择奇数项的数目=方式数目拒绝奇品=方式选择偶数号

您还可以通过仅保留2个DP阵列中的列和重用他们为 DP优化空间[I-2] [X] 将被丢弃。

Given an array, arr, of length n, find how many subsets of arr there are such that XOR(^) of those subsets is equal to a given number, ans.

I have this dp approach but is there a way to improve its time complexity. ans is always less than 1024.

Here ans is the no. such that XOR(^) of the subsets is equal to it. arr[n] contains all the numbers

memset(dp, 0, sizeof(dp));
dp[0][0] = 1;

for(i = 1; i <= n; i++){
    for(j = 0; j < 1024; j++) {
        dp[i][j] = (dp[i-1][j] + dp[i-1][j^arr[i]]);
    }
}

cout << (dp[n][ans]);

解决方案

From user3386109's comment, building on top of your code:

/* Warning: Untested */
int counts[1024] = {0}, ways[1024];
for(int i = 1; i <= n; ++i) counts[ arr[i] ] += 1;
for(int i = 0; i <= 1024; ++i) {
  const int z = counts[i];
  // Look for overflow here
  ways[i] = z == 0 ?
              0 :
              (int)(1U << (z-1));
}

memset(dp, 0, sizeof(dp));
dp[0][0] = 1;

for(i = 1; i <= 1024; i++){
    for(j = 0; j < 1024; j++) {
        // Check for overflow
        const int howmany = ways[i] * dp[i-1][j];
        dp[i][j] += howmany;
        dp[i][j^i] += howmany;
    }
}

cout << (dp[1024][ans]);

For calculating odd_ and even_, you can also use the following:

ⁿc₀+ⁿc₂+... = ⁿc₁+ⁿc₃... = 2^n-1

Because number of ways to select odd items = number of ways to reject odd items = number of ways to select even numbers

You can also optimize the space by keeping just 2 columns of dp arrays and reusing them as dp[i-2][x] are discarded.

这篇关于给定长度n的阵列，找到子集的数目，其中一个子集的异或等于给定数量的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！