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
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
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 +}