Artifact Content
Not logged in

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;
}