Badxor subset problem

#1


plz have a look on this que it give tle when we creat all subsets and then checking , so how to apply dp??

#2

Hey @Ashu1318 instead of finding good subsets find bad subsets and subtract them from total number of subsets

#3

but that will also take o(n3) tc ,i want to know how to implement dp here

#4

Let dp[i][j] represent the number of subsets formed from the first i elements that have a bitwise xor exactly equal to j. For calculating dp[i][j], either you pick ith element in your subset, or you don’t, so dp[i][j] = dp[i-1][j] + dp[i-1][j^arr[i]]. Your answer will be summation of all dp[n][j] such that j!=b.
Then you can use unordered_set for checking occurence of B[i] in O(1) time.
Also, try using scanf and printf on SPOJ because cin and cout occasionally gives Time Limit Exceeded(only on SPOJ, other platforms accept it).

Here’s my code. It is accepted on SPOJ.

#5

okay okay now i got it thanks .