kyopro-lib

This documentation is automatically generated by online-judge-tools/verification-helper

View on GitHub

:heavy_check_mark: test/aoj/2530/main.test.cpp

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2530"

#include <bitset>
#include <iostream>
#include <vector>
#include "Mylib/IO/input_vector.cpp"
#include "Mylib/LinearAlgebra/simultaneous_linear_equations_binary.cpp"
#include "Mylib/Number/Mod/mod_pow.cpp"

namespace hl = haar_lib;

constexpr int64_t mod = 1000000009;
using B               = std::bitset<2500>;

int main() {
  int R, C;
  std::cin >> R >> C;

  auto f = hl::input_vector<int>(R, C);

  std::vector<std::vector<int>> index(R, std::vector<int>(C));
  {
    int c = 0;
    for (int i = 0; i < R; ++i) {
      for (int j = 0; j < C; ++j) {
        index[i][j] = c;
        ++c;
      }
    }
  }

  std::vector<B> a(R * C);
  std::vector<bool> b(R * C);

  for (int i = 0; i < R; ++i) {
    for (int j = 0; j < C; ++j) {
      b[index[i][j]] = f[i][j];

      for (int p = 0; p < R; ++p) {
        for (int q = 0; q < C; ++q) {
          if (abs(i - p) == abs(j - q) or i == p or j == q) {
            a[index[p][q]][index[i][j]] = true;
          }
        }
      }
    }
  }

  auto res = hl::binary_simultaneous_linear_equations(a, b);

  int64_t ans = 0;
  if (res) {
    ans = hl::mod_pow(2, R * C - (*res).rank, mod);
  }

  std::cout << ans << std::endl;

  return 0;
}
#line 1 "test/aoj/2530/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2530"

#include <bitset>
#include <iostream>
#include <vector>
#line 4 "Mylib/IO/input_vector.cpp"

namespace haar_lib {
  template <typename T>
  std::vector<T> input_vector(int N) {
    std::vector<T> ret(N);
    for (int i = 0; i < N; ++i) std::cin >> ret[i];
    return ret;
  }

  template <typename T>
  std::vector<std::vector<T>> input_vector(int N, int M) {
    std::vector<std::vector<T>> ret(N);
    for (int i = 0; i < N; ++i) ret[i] = input_vector<T>(M);
    return ret;
  }
}  // namespace haar_lib
#line 3 "Mylib/LinearAlgebra/simultaneous_linear_equations_binary.cpp"
#include <optional>
#include <utility>
#line 6 "Mylib/LinearAlgebra/simultaneous_linear_equations_binary.cpp"

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/Number/Mod/mod_pow.cpp"
#include <cstdint>

namespace haar_lib {
  constexpr int64_t mod_pow(int64_t n, int64_t p, int64_t m) {
    int64_t ret = 1;
    while (p > 0) {
      if (p & 1) (ret *= n) %= m;
      (n *= n) %= m;
      p >>= 1;
    }
    return ret;
  }
}  // namespace haar_lib
#line 9 "test/aoj/2530/main.test.cpp"

namespace hl = haar_lib;

constexpr int64_t mod = 1000000009;
using B               = std::bitset<2500>;

int main() {
  int R, C;
  std::cin >> R >> C;

  auto f = hl::input_vector<int>(R, C);

  std::vector<std::vector<int>> index(R, std::vector<int>(C));
  {
    int c = 0;
    for (int i = 0; i < R; ++i) {
      for (int j = 0; j < C; ++j) {
        index[i][j] = c;
        ++c;
      }
    }
  }

  std::vector<B> a(R * C);
  std::vector<bool> b(R * C);

  for (int i = 0; i < R; ++i) {
    for (int j = 0; j < C; ++j) {
      b[index[i][j]] = f[i][j];

      for (int p = 0; p < R; ++p) {
        for (int q = 0; q < C; ++q) {
          if (abs(i - p) == abs(j - q) or i == p or j == q) {
            a[index[p][q]][index[i][j]] = true;
          }
        }
      }
    }
  }

  auto res = hl::binary_simultaneous_linear_equations(a, b);

  int64_t ans = 0;
  if (res) {
    ans = hl::mod_pow(2, R * C - (*res).rank, mod);
  }

  std::cout << ans << std::endl;

  return 0;
}
Back to top page