给定长度n的阵列，找到子集的数目，其中一个子集的异或等于给定数量的

问题描述

给定一个数组

，改编，长度 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] [答]）;
 

解决方案

从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]）;
 

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

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的阵列，找到子集的数目，其中一个子集的异或等于给定数量的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！