本文介绍了给定长度n的阵列,找到子集的数目,其中一个子集的异或等于给定数量的的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
给定一个数组,改编
,长度 N
,找到多少的子集ARR
有这样 XOR(^)
的子集是等于给定的数字,答
。
我有这样的 DP
的方法,但有改善其时间复杂度的一种方式。 答
总是小于1024。
下面答
是否定的。这样 XOR(^)
子集等于它。改编[N]
包含了所有的数字
memset的(DP,0,sizeof的(DP));
DP [0] [0] = 1;对于(i = 1; I< = N;我++){
为(J = 0; J< 1024; J ++){
DP [I] [j]的=(DP [I-1] [j]的+ DP [I-1] [J ^改编由[i]]);
}
}COUT<< (DP [N] [答]);
解决方案
从user3386109's发表评论,建立在你的code的顶部:
/ *警告:未经测试* /
INT计[1024] = {0},方法[1024];
的for(int i = 1; I< = N; ++ i)统计[ARR [I] + = 1;
的for(int i = 0; I< = 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< = 1024;我++){
为(J = 0; J< 1024; J ++){
//检查溢出
const int的的howmany =方式[I] * DP [I-1] [J]。
DP [I] [J] + =的howmany;
DP [I] [J ^ I] + =的howmany;
}
}COUT<< (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的阵列,找到子集的数目,其中一个子集的异或等于给定数量的的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!