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