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?
3. Can someone please help correct the following implementation?
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;
}