Artifact 194d05c14bae2d3f93fb64427541028d31ba3442
//-------------------------------------------------------------
// Linear Equation Number of Solutions. (GF(2))
// O(n^3)
//
// Verified by
// - SRM 590 Div1 LV2
//
// M[H][W] x = V[H]
//-------------------------------------------------------------
LL num_solution(int H, int W, vector<vector<int>> M, vector<int> V)
{
int skipx = 0;
int y = 0;
for(int x=0; y<H && x<W; ++x)
{
if(M[y][x] == 0) {
bool found = false;
for(int yy=y+1; yy<H; ++yy)
if(M[yy][x] == 1) {
swap(M[y], M[yy]);
swap(V[y], V[yy]);
found = true;
break;
}
if(!found) {
++skipx;
continue;
}
}
for(int yy=y+1; yy<H; ++yy)
if(M[yy][x] == 1) {
for(int xx=x; xx<W; ++xx)
M[yy][xx] ^= M[y][xx];
V[yy] ^= V[y];
}
++y;
}
for(int yy=y; yy<H; ++yy)
if(V[yy] == 1)
return 0;
return 1LL << skipx;
}