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.

# | User | Rating |
---|---|---|

1 | tourist | 3707 |

2 | Benq | 3672 |

3 | ksun48 | 3575 |

4 | Radewoosh | 3562 |

5 | Miracle03 | 3480 |

6 | maroonrk | 3406 |

7 | ecnerwala | 3400 |

8 | peehs_moorhsum | 3384 |

9 | sunset | 3338 |

10 | Um_nik | 3320 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 208 |

2 | YouKn0wWho | 197 |

2 | Um_nik | 197 |

4 | Errichto | 181 |

4 | sus | 181 |

6 | awoo | 179 |

7 | tourist | 175 |

8 | -is-this-fft- | 171 |

8 | SecondThread | 171 |

10 | Ashishgup | 170 |

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.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/27/2021 04:43:39 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

What is the range of elements ?

10^5

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)`

.I know the solution for contiguous substrings but I want for not contiguous. Anyway , thank you!

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

OK , this solution is in O(n^2) , but i want in O(nlogn) or something like this.

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?

Ok , but it isn't optimal good. N <= 10 ^ 5 or something like this

ignore

can u give me the link of problem?

There isn't a problem... I thought at this, some time and i didn't find a good solution, so I published this post.

hah :D my case is similar link.

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).