### -synx-'s blog

By -synx-, history, 5 years ago, e-maxx
This link mentions that we can speed up conventional Gaussian elimination by using bitset
to achieve O(n3 / 32) using bitwise operations.
I have 3 questions:
1. Do they mean mod 2 inverses (1 + 1 = 0, 0 + 0 = 0, 0 + 1 = 1 + 0 = 1)?
2. For mod 2 inverse to exist, does this imply det(A) mod 2 ≠ 0?

vector<bitset<N>>gaussModTwo(vector<bitset<N>>a,vector<bitset<N>>b){
int n=a.size(), i, j;
for(i=0;i<n;++i){
for(j=i;j<n;++j) if(a[j][i]){
swap(a[j],a[i]);
swap(b[j],b[i]);
break;
}
for(j=0;j<n;++j) if(j!=i) {
a[j]^=a[i];
b[j]^=b[i];
}
}
return b;
} Comments (1)
 » Can anyone help? Help is appreciated.
{"ft_lang_label":"__label__en","ft_lang_prob":0.5889391,"math_prob":0.98505086,"size":656,"snap":"2021-43-2021-49","text_gpt3_token_len":230,"char_repetition_ratio":0.10429448,"word_repetition_ratio":0.0,"special_character_ratio":0.38567072,"punctuation_ratio":0.19075145,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99956065,"pos_list":[0,1,2,3,4,5,6],"im_url_duplicate_count":[null,1,null,1,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-12-06T18:55:07Z\",\"WARC-Record-ID\":\"<urn:uuid:52a0f884-4d86-4ed7-b31f-ce71d858da62>\",\"Content-Length\":\"85281\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:ecbdcd6e-e92f-45f2-ae69-b165ee9cefd9>\",\"WARC-Concurrent-To\":\"<urn:uuid:b7e709bf-5964-4c5c-a814-dfde69683cbd>\",\"WARC-IP-Address\":\"213.248.110.126\",\"WARC-Target-URI\":\"https://codeforces.com/blog/entry/52270\",\"WARC-Payload-Digest\":\"sha1:OJA3GDDGPYU77F6RAUONI36SWEQLY6LH\",\"WARC-Block-Digest\":\"sha1:FP7C62VQAXIJKY3OIRPYHCWE36EK7OM2\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-49/CC-MAIN-2021-49_segments_1637964363309.86_warc_CC-MAIN-20211206163944-20211206193944-00443.warc.gz\"}"}