### Tudor's blog

By Tudor, history, 6 years ago,

It is an array with n elements and d[i] = how many substrings have XOR value i. What is the optimal algorithm for build this dp? substring = a[i1] , a[i2] , ... not contigous.

• +11

 » 6 years ago, # |   0 What is the range of elements ?
•  » » 6 years ago, # ^ |   0 10^5
 » 6 years ago, # |   0 In the beginning you mention substrings, then in the end "not contiguous". By the way, if you're interested in contiguous substrings with their XOR equals to a value X: 1) Create a trie with all XOR prefixes of values in array A. 2) Take advantage of XOR associativity property and then, for each prefix, search for an value inside the trie which it's value XOR the current prefix would lead to X. Insertion on trie is O(N*L) with L as the number of bits of the value. As the maximum value is 32, insertions and queries are negligible. The overall complexity is O(n).
•  » » 6 years ago, # ^ |   0 I know the solution for contiguous substrings but I want for not contiguous. Anyway , thank you!
 » 6 years ago, # | ← Rev. 2 →   0 Take a dp[n][xor] which stores the number of substrings having xor value 'xor' starting at index i; start iterating over the string from the end. dp[i][x]=dp[i+1][a[i]^x]; for non contiguous, use the idea of inclusion exclusion dp[i][x]=dp[i+1][x]+dp[i+1][x^a[i]];
•  » » 6 years ago, # ^ |   0 OK , this solution is in O(n^2) , but i want in O(nlogn) or something like this.
•  » » » 6 years ago, # ^ |   0 not o(n^2), more like ~ o(n * max_a) where max_a is the biggest element in the array. That complexity can be worse or better depending on the constrains. How big are the constrains for the elements and for N?
•  » » » » 6 years ago, # ^ |   0 Ok , but it isn't optimal good. N <= 10 ^ 5 or something like this
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 ignore
 » 6 years ago, # |   0 can u give me the link of problem?
•  » » 6 years ago, # ^ |   +3 There isn't a problem... I thought at this, some time and i didn't find a good solution, so I published this post.
•  » » » 6 years ago, # ^ |   0 hah :D my case is similar link.
 » 6 years ago, # |   0 Use Gaussian Elimination to find a basis for the space spanned by the N vectors. Let R be its rank. Add the vector i to the basis, and use Gauss again to check whether the rank increased. If it did, the answer is 0, since i is not in the space spanned by the elements of the original array. If adding i didn't increase the rank, the answer is 2 ^ (# of free variables); that is, 2 ^ (N — R).