• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

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

   34                          for(int k=i; k<n; ++k)                                        34                          for(int k=i; k<n; ++k)
   35                                  M[j][k] -= M[i][k] * r;                               35                                  M[j][k] -= M[i][k] * r;
   36                          A[j] -= A[i] * r;                                             36                          A[j] -= A[i] * r;
   37                  }                                                                     37                  }
   38          }                                                                             38          }
   39          return A;                                                                     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  }