Subset xor problem (need help)

Правка en2, от skavurskaa, 2016-04-01 18:17:22

I am solving a problem where a set of N K-bit integers is given (N <= 10^4, K <= 50). I am allowed to do a single operation: choose two numbers A,B from the set and insert A xor B into the set.

The problem asks if it is possible, for the given set, to generate all numbers from 0 to 2K - 1 using only this operation, as many times as i want.

I read that this can be solved using Gaussian Elimination, but i don't know how to do it. Can any one help me with this problem? Thx in advance :)

EDIT : I solved the problem. Thanks to Enchom for the awesome algorithm! To the ones interested, here are the original problem statement and my solution:

https://www.urionlinejudge.com.br/judge/en/problems/view/1942

http://pastebin.com/aXmLB8Ud

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский skavurskaa 2016-04-01 18:17:22 275 problem solved
en1 Английский skavurskaa 2016-04-01 02:39:17 525 Initial revision (published)