cantsolvediv2C's blog

Inverse of finding Xor Basis ?
By cantsolvediv2C, history, 15 months ago, In English

Hello Codeforces community! Hope you all are doing well.

I need some help with the following question that I had while understanding xor basis.

Given an array A. You need to tell how many arrays B of length n exist that satisfy the following property: For each A[i], a subset of B exist such that its xor is equal to A[i] and 0 <= B[i] < 2^k.

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Well, you can find the xor basis $$$M$$$ of the given set of vectors $$$A$$$.

If $$$n-|M| \lt 0$$$, then 0 solutions. ( I'll assume this is not possible, because $$$\textbf{n}$$$ that you mention must be the size of array $$$A$$$ )

If $$$n-|M| \gt 0$$$, then there would be infinite solutions really, since you can choose the extra elements freely

I'm not sure how to tackle the case when $$$n-|M| = 0$$$, seems tricky.

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh, I forgot to mention an important constraint: 0 <= A[i], B[i] < 2^k. Thanks.

    → Reply