Author: | Pavle Martinović |
Solved by: | |
First to solve: | Sigma-=-1 |
The first insight is that we will actually want to calculate the number of sets that do include their own XOR and subtract that number from the total number of sets. A set includes its own XOR if and only if it’s gotten by adding exactly one element to a set with XOR equal to . Now we are interested in the sum "how many times is an element outside a set of XOR ".
Firstly, we are interested in the number of sets with XOR . This is well known if we have a vector basis: 2^{N-basis\_size}.
Lemma: Let be the family of all subsets of of with XOR 0. Every element x\in A is in either or \frac{|\Phi|}{2} elements of .
Proof: Suppose that an element is in a subset of with XOR . Then we can construct a bijection between the XOR subsets that include and those that don’t - just take the set XOR of that set and ! Indeed, this will keep the XOR , remove if it is in , and add it in if it is not. This means that every element is in either XOR subsets (if does not exist) or precisely half.
Now, to calculate everything, we just need the number of elements that are precisely in XOR sets (with a basis everything can be calculated with this info). The key insight here is that those elements have to be in the basis of the set, because all others can be represented using the elements that are in the basis so taking that representation plus that element generates at least one such set. Furthermore, the only way to have an element with no XOR subset containing it is for it to never be used in the representation of any element of the set outside the basis, because if such an element exists, taking the set containing it and its representation would produce one such set.
So to fully solve this, we just add elements one by one and maintain the basis. When we represent the elements outside the basis, we also memorize the number of elements from the basis that are never used.