XOR basis without linear algebra

Revision en1, by Everule, 2022-02-17 22:48:03

I think that linear algebra, is a unnecessarily intimidating tool, to solve a problem I believe is far easier, and needlessly intimidates those without formal knowledge of linear algebra, which is a significant part of codeforces. I know I did. Therefore I want to show a step by step problem solving process that will lead to the concept of linear basis at the end, with no formal knowledge required.

We start with the elementary problem of linear basis. Given an array $$$[a_1, a_2, \ldots a_n]$$$, where $$$a_i \le 2^d$$$, find the number of distinct

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English Everule 2022-02-18 01:05:10 95
en8 English Everule 2022-02-18 00:16:13 53
en7 English Everule 2022-02-18 00:12:06 3 Tiny change: 'know I did. Therefor' -> 'know I didn't. Therefor'
en6 English Everule 2022-02-18 00:02:46 2 Tiny change: 'g this to O(d) as an exe' -> 'g this to $O(d)$ as an exe' (published)
en5 English Everule 2022-02-17 23:59:34 22
en4 English Everule 2022-02-17 23:57:49 1288
en3 English Everule 2022-02-17 23:39:27 801 Tiny change: 'ldots, a_k$ and simi' -> 'ldots, a_k]$ and simi'
en2 English Everule 2022-02-17 23:26:38 3452 Tiny change: 'plus x \bihoplus y = ' -> 'plus x \bigoplus y = '
en1 English Everule 2022-02-17 22:48:03 581 Initial revision (saved to drafts)