Check-in [ab609d305d]
Not logged in
Overview
SHA1 Hash:ab609d305d261f575c519b212ec07788e1f7b583
Date: 2013-09-07 18:33:30
User: kinaba
Comment:Number of linear equation solutions in GF2.
Timelines: family | ancestors | descendants | both | trunk
Downloads: Tarball | ZIP archive
Other Links: files | file ages | manifest
Tags And Properties
Changes

Modified lib/numeric/linearEq.cpp from [908cbaac8fbb72e4] to [ad8998bb99a43250].

34 34 for(int k=i; k<n; ++k) 35 35 M[j][k] -= M[i][k] * r; 36 36 A[j] -= A[i] * r; 37 37 } 38 38 } 39 39 return A; 40 40 } 41 + 42 +

Added lib/numeric/linearEq_numsol.cpp version [194d05c14bae2d3f]

1 + 2 +//------------------------------------------------------------- 3 +// Linear Equation Number of Solutions. (GF(2)) 4 +// O(n^3) 5 +// 6 +// Verified by 7 +// - SRM 590 Div1 LV2 8 +// 9 +// M[H][W] x = V[H] 10 +//------------------------------------------------------------- 11 + 12 +LL num_solution(int H, int W, vector<vector<int>> M, vector<int> V) 13 +{ 14 + int skipx = 0; 15 + int y = 0; 16 + for(int x=0; y<H && x<W; ++x) 17 + { 18 + if(M[y][x] == 0) { 19 + bool found = false; 20 + for(int yy=y+1; yy<H; ++yy) 21 + if(M[yy][x] == 1) { 22 + swap(M[y], M[yy]); 23 + swap(V[y], V[yy]); 24 + found = true; 25 + break; 26 + } 27 + if(!found) { 28 + ++skipx; 29 + continue; 30 + } 31 + } 32 + 33 + for(int yy=y+1; yy<H; ++yy) 34 + if(M[yy][x] == 1) { 35 + for(int xx=x; xx<W; ++xx) 36 + M[yy][xx] ^= M[y][xx]; 37 + V[yy] ^= V[y]; 38 + } 39 + ++y; 40 + } 41 + 42 + for(int yy=y; yy<H; ++yy) 43 + if(V[yy] == 1) 44 + return 0; 45 + return 1LL << skipx; 46 +}