Віслюче, стій на варті#12978

Віслюче, стій на варті (Розбір)

Author:

Pavle Martinović

Solved by:

First to solve:

N/A

We split into two cases, whether is even or odd.

Case 1: is even. Let’s look at each bit independently. If the bit is set in any element of , we know it will exist in the . This bit will exist in the if it’s set in every element of , and since is even, then it won’t be set in the . So every bit set in the is set in at most one of , so \text{AND}(s)+\text{XOR}(s)\leq\text{OR}(s). The equality is attained only when each bit is set everywhere, nowhere or in an odd number of elements (these are three distinct cases).

Let’s fix a ternary mask of size (being the log of ), containing , and . This mask represents that we want to select some subsequence such that:

We also have to ensure that the set is of even size. Let be the multiset of elements of that follow the pattern made by the ternary mask. Now we just need to find the number of even subsets of that such that their xor is equal to one on the positions. If our mask has positions with a , suppose we look at every element in as a vector in \mathbb{F}_2^{m+1} with entries corresponding to entries of those elements in the positions, and also one at the end to keep track of parity. We need to find the number of subsets of these vectors summing to (1,1,\ldots,1,1,0) (the ones at the first positions mean that the is on the positions; the zero at the end means that there is an even number of elements). By linear algebra (for example, the Rank-Nullity Theorem) we know that the number of such subsets is either or 2^{|B|-d}, where is the dimension of the subspace generated by the elements of . The way we can check whether the answer is we need to find the basis generated by set (by Gaussian elimination), and simply check whether we can obtain it (by doing this we also find the value of ). Once we check whether we can get it, we add 2^{|B|-d}. If m=0 we actually add 2^{|B|-d}-1 because we don’t want to count the empty set.

Now the question becomes how do we find the basis for each mask? Doing this naively can be done in O(n\cdot \max a_i\cdot15) or O(\max a_i^2\cdot 15), which are too slow. The trick is to iterate through all the masks, and find the new basis through old ones. Let’s look at one of the mask. First we replace the with a then a , to get to new masks mask_0 and mask_1. Intuitively, it makes sense we can find the basis for mask when we know the bases for mask_0 and mask_1. It can be tempting to do this by appending a to the beginning of every vector in the basis mask_0 and a to the beginning of every vector in the basis mask_1 and finding the basis of this set. This however won’t give us a correct basis, since the we appended at the beginning of the vectors for mask_1 can become a during Gaussian elimination. The trick is that we actually know what this bit should be for each vector in the basis for mask_1, because we already know what happened to a bit appended to always be in the Gaussian elimination for mask_1: it’s the last bit we added to track parity! So actually, we append to the beginning of every vector in the basis of mask_0 and the last entry (parity entry) to the beginning of every vector in the basis of mask_1, and merge them using Gaussian elimination.

Case 2: is odd. This is in some sense the harder case, but we will use a lot of the same ideas. First to identify what the bits look like. Here it is more uncomfortable since if has some bit set, then so does . So for each bit set in , it can be set zero, one or two times on the left side. Subtracting the right side of the equation from the left we get \sum \pm2^{i_k}=0, where all i_k are distinct, which is possible only if the sum is empty (because binary representation is unique). So the only possible way is for each bit set in the to be set only in i.e. each bit is either set nowhere or set in some odd number of elements but not all of them.

Now suppose we take a mask like last time, but now consisting only of and . Let B\subset A the elements matching this pattern restricted to the positions again. We need the number of subsets of odd subsets of that xor to (1,1,1\ldots,1,1) and no bit is contained in all of them. This second condition is impossible to model using linear algebra. Best we can do is find the total number of such subsets (appending by again to ensure its parity) and try to take away the sets which contain bits that are set in every element.

The way we do this is the principle of inclusion-exclusion. Let’s again take our ternary masks like in the previous case. We find the number of sets that have all zeros and ones on those positions, and has an odd number of ones on all positions. Then we add (-1)^{\text{(\# of 1s)}}*2^{|B|-d} to the solution if we pass the check. Let’s see what happens to a set that doesn’t have any bit set to 1 everywhere. It’s counted just once, for the mask with only and . If a set has exactly bits which are 1 everywhere, then it’s counted 2^k times, but since we alternate signs, we actually count it \sum(-1)^t\binom{k}{t}=0 times. So we counted everything the correct amount of times.

We now may solve this case in parallel with the first case. Once we obtain the basis for some mask, we check whether we can get (1,1,\ldots,1,0) and if needed we can add the adequate amount from the first case to the solution, and then check whether we can get (1,1,\ldots,1,1) and if needed we add the amount from the second case. The complexity of this solution is O(3^k\cdot k^2) where k=\log_2\max a_i (more precisely O(n+\max a_i^{1.58}\log(\max a_i)^2)) with the only part actually having log squared being merging bases). However, when calculating how many operations we actually need (summing the number of squared for each mask) we get about 1.2\cdot 10^8, which runs very quickly, especially that we use the xor operation in the Gaussian elimination for merging bases. The rest of the solution works in O(3^k\cdot k).