Artifact 194d05c14bae2d3f93fb64427541028d31ba3442:
0000: 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d .//-------------
0010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0040: 0a 2f 2f 20 4c 69 6e 65 61 72 20 45 71 75 61 74 .// Linear Equat
0050: 69 6f 6e 20 4e 75 6d 62 65 72 20 6f 66 20 53 6f ion Number of So
0060: 6c 75 74 69 6f 6e 73 2e 20 28 47 46 28 32 29 29 lutions. (GF(2))
0070: 0a 2f 2f 20 20 20 4f 28 6e 5e 33 29 0a 2f 2f 0a .// O(n^3).//.
0080: 2f 2f 20 56 65 72 69 66 69 65 64 20 62 79 0a 2f // Verified by./
0090: 2f 20 20 20 2d 20 53 52 4d 20 35 39 30 20 44 69 / - SRM 590 Di
00a0: 76 31 20 4c 56 32 0a 2f 2f 0a 2f 2f 20 4d 5b 48 v1 LV2.//.// M[H
00b0: 5d 5b 57 5d 20 78 20 3d 20 56 5b 48 5d 0a 2f 2f ][W] x = V[H].//
00c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 0a 4c -------------..L
0100: 4c 20 6e 75 6d 5f 73 6f 6c 75 74 69 6f 6e 28 69 L num_solution(i
0110: 6e 74 20 48 2c 20 69 6e 74 20 57 2c 20 76 65 63 nt H, int W, vec
0120: 74 6f 72 3c 76 65 63 74 6f 72 3c 69 6e 74 3e 3e tor<vector<int>>
0130: 20 4d 2c 20 76 65 63 74 6f 72 3c 69 6e 74 3e 20 M, vector<int>
0140: 56 29 0a 7b 0a 09 69 6e 74 20 73 6b 69 70 78 20 V).{..int skipx
0150: 3d 20 30 3b 0a 09 69 6e 74 20 79 20 3d 20 30 3b = 0;..int y = 0;
0160: 0a 09 66 6f 72 28 69 6e 74 20 78 3d 30 3b 20 79 ..for(int x=0; y
0170: 3c 48 20 26 26 20 78 3c 57 3b 20 2b 2b 78 29 0a <H && x<W; ++x).
0180: 09 7b 0a 09 09 69 66 28 4d 5b 79 5d 5b 78 5d 20 .{...if(M[y][x]
0190: 3d 3d 20 30 29 20 7b 0a 09 09 09 62 6f 6f 6c 20 == 0) {....bool
01a0: 66 6f 75 6e 64 20 3d 20 66 61 6c 73 65 3b 0a 09 found = false;..
01b0: 09 09 66 6f 72 28 69 6e 74 20 79 79 3d 79 2b 31 ..for(int yy=y+1
01c0: 3b 20 79 79 3c 48 3b 20 2b 2b 79 79 29 0a 09 09 ; yy<H; ++yy)...
01d0: 09 09 69 66 28 4d 5b 79 79 5d 5b 78 5d 20 3d 3d ..if(M[yy][x] ==
01e0: 20 31 29 20 7b 0a 09 09 09 09 09 73 77 61 70 28 1) {......swap(
01f0: 4d 5b 79 5d 2c 20 4d 5b 79 79 5d 29 3b 0a 09 09 M[y], M[yy]);...
0200: 09 09 09 73 77 61 70 28 56 5b 79 5d 2c 20 56 5b ...swap(V[y], V[
0210: 79 79 5d 29 3b 0a 09 09 09 09 09 66 6f 75 6e 64 yy]);......found
0220: 20 3d 20 74 72 75 65 3b 0a 09 09 09 09 09 62 72 = true;......br
0230: 65 61 6b 3b 0a 09 09 09 09 7d 0a 09 09 09 69 66 eak;.....}....if
0240: 28 21 66 6f 75 6e 64 29 20 7b 0a 09 09 09 09 2b (!found) {.....+
0250: 2b 73 6b 69 70 78 3b 0a 09 09 09 09 63 6f 6e 74 +skipx;.....cont
0260: 69 6e 75 65 3b 0a 09 09 09 7d 0a 09 09 7d 0a 0a inue;....}...}..
0270: 09 09 66 6f 72 28 69 6e 74 20 79 79 3d 79 2b 31 ..for(int yy=y+1
0280: 3b 20 79 79 3c 48 3b 20 2b 2b 79 79 29 0a 09 09 ; yy<H; ++yy)...
0290: 09 69 66 28 4d 5b 79 79 5d 5b 78 5d 20 3d 3d 20 .if(M[yy][x] ==
02a0: 31 29 20 7b 0a 09 09 09 09 66 6f 72 28 69 6e 74 1) {.....for(int
02b0: 20 78 78 3d 78 3b 20 78 78 3c 57 3b 20 2b 2b 78 xx=x; xx<W; ++x
02c0: 78 29 0a 09 09 09 09 09 4d 5b 79 79 5d 5b 78 78 x)......M[yy][xx
02d0: 5d 20 5e 3d 20 4d 5b 79 5d 5b 78 78 5d 3b 0a 09 ] ^= M[y][xx];..
02e0: 09 09 09 56 5b 79 79 5d 20 5e 3d 20 56 5b 79 5d ...V[yy] ^= V[y]
02f0: 3b 0a 09 09 09 7d 0a 09 09 2b 2b 79 3b 0a 09 7d ;....}...++y;..}
0300: 0a 0a 09 66 6f 72 28 69 6e 74 20 79 79 3d 79 3b ...for(int yy=y;
0310: 20 79 79 3c 48 3b 20 2b 2b 79 79 29 0a 09 09 69 yy<H; ++yy)...i
0320: 66 28 56 5b 79 79 5d 20 3d 3d 20 31 29 0a 09 09 f(V[yy] == 1)...
0330: 09 72 65 74 75 72 6e 20 30 3b 0a 09 72 65 74 75 .return 0;..retu
0340: 72 6e 20 31 4c 4c 20 3c 3c 20 73 6b 69 70 78 3b rn 1LL << skipx;
0350: 0a 7d 0a .}.