Simultaneous linear equations (Mod2)
(Mylib/LinearAlgebra/simultaneous_linear_equations_binary.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

Requirements

Notes

Problems

References

Verified with

• test/aoj/1308/main.test.cpp
• test/aoj/2530/main.test.cpp

Code

#pragma once
#include <bitset>
#include <optional>
#include <utility>
#include <vector>

namespace haar_lib {
  namespace binary_simultaneous_linear_equations_impl {
    template <size_t N>
    struct result {
      int rank, dim;
      std::vector<bool> solution;
    };
  }  // namespace binary_simultaneous_linear_equations_impl

  template <size_t N>
  auto binary_simultaneous_linear_equations(std::vector<std::bitset<N>> a, std::vector<bool> b) {
    using result = binary_simultaneous_linear_equations_impl::result<N>;
    std::optional<result> ret;

    const int n = a.size(), m = N;
    int rank = 0;

    for (int j = 0; j < m; ++j) {
      int pivot = -1;
      for (int i = rank; i < n; ++i) {
        if (a[i][j]) {
          pivot = i;
          break;
        }
      }

      if (pivot == -1) continue;
      std::swap(a[pivot], a[rank]);
      swap(b[pivot], b[rank]);

      for (int i = 0; i < n; ++i) {
        if (i != rank and a[i][j]) {
          a[i] ^= a[rank];
          b[i] = b[i] ^ b[rank];
        }
      }

      ++rank;
    }

    for (int i = rank; i < n; ++i) {
      if (b[i]) {
        return ret;
      }
    }

    const int dim = m - rank;

    std::vector<bool> solution(m);
    for (int i = 0; i < rank; ++i) solution[i] = b[i];

    ret = result({rank, dim, solution});
    return ret;
  }
}  // namespace haar_lib

#line 2 "Mylib/LinearAlgebra/simultaneous_linear_equations_binary.cpp"
#include <bitset>
#include <optional>
#include <utility>
#include <vector>

namespace haar_lib {
  namespace binary_simultaneous_linear_equations_impl {
    template <size_t N>
    struct result {
      int rank, dim;
      std::vector<bool> solution;
    };
  }  // namespace binary_simultaneous_linear_equations_impl

  template <size_t N>
  auto binary_simultaneous_linear_equations(std::vector<std::bitset<N>> a, std::vector<bool> b) {
    using result = binary_simultaneous_linear_equations_impl::result<N>;
    std::optional<result> ret;

    const int n = a.size(), m = N;
    int rank = 0;

    for (int j = 0; j < m; ++j) {
      int pivot = -1;
      for (int i = rank; i < n; ++i) {
        if (a[i][j]) {
          pivot = i;
          break;
        }
      }

      if (pivot == -1) continue;
      std::swap(a[pivot], a[rank]);
      swap(b[pivot], b[rank]);

      for (int i = 0; i < n; ++i) {
        if (i != rank and a[i][j]) {
          a[i] ^= a[rank];
          b[i] = b[i] ^ b[rank];
        }
      }

      ++rank;
    }

    for (int i = rank; i < n; ++i) {
      if (b[i]) {
        return ret;
      }
    }

    const int dim = m - rank;

    std::vector<bool> solution(m);
    for (int i = 0; i < rank; ++i) solution[i] = b[i];

    ret = result({rank, dim, solution});
    return ret;
  }
}  // namespace haar_lib

Back to top page