egor_bb's blog

By egor_bb, history, 3 weeks ago,

Hi! There is a practical problem that reduces to the following:

You are given some 2N-bit strings that generate a group with XOR operation (subgroup of all 2N-bit strings). The goal is to find the number of elements in the group satisfying the following property in any reasonable time:

• Split the 2N-bit string into N pairs of adjacent bits, for example $01111011 > (01)(11)(10)(11)$
• The number of $(11)$ pairs should be odd (in the example there are two such pairs, so we don’t count it)

The faster the better, but ideas on speeding up the brute force are also welcome. I’m stuck at the moment and don’t even understand how to Google it properly :(