Its there in the practice section now.

Consider how many times the i-th bit (where 0 ≤ i < 20) shows up in all of the bitwise XOR's. You should see a pattern!

For example, consider N = 2 with the sequence consisting of 3 = 011₂ and 4 = 100₂.

The last bit shows up three times:

Similarly, the 2nd-to-last and first bit show up three times as well.

So the total beauty is

If you have a sequence of k ones and n - k zeroes, the sum of lengths of sequences with xor = 1 is given by the derivative of:

at x = 1

It breaks into three cases :

• . The number of such sequences is a = 1.
• . The number of such sequences is b = n.
• . The number of such sequences is c = 2ⁿ - n - 1.

Now, we have these sequences for all bit positions. Say the mask of positions with k = 0 is m₀, and mask of positions with k = 1 is m₁, and mask of positions with k ≥ 2 is m₂, then:

n2^n - 2(M - m₀) + m₁2^n - 2 = b

We can iterate over all submasks m₀ of M, and use modular inverse to find m₁. Accept this pair (m₀, m₁) if and only if m₀&m₁ = 0 and m₀|m₁ is a submask of M. m₂ = M - m₀ - m₁. If x₀, x₁, x₂ is the number of set bits in m₀, m₁, m₂ respectively, then we add a^x₀b^x₁c^x₂ to the answer.

Solution Link

Expected solution is to convert it to a flow network with O(M+N) vertices and O(M+N) edges and compute flow in it. Some Hopcroft Karp and brute force matching(which should have given TLE) ran much faster than expected,

This happened to me and I just ignored it, but my solution was wrong! So much for solving all problems D:

Link

Yes they messed up scoring for that problem.