2進数上の行列演算
(atcoder/bitmatrix.hpp)

• View this file on GitHub
• Last update: 2021-10-25 12:05:31+09:00
• Include: #include "atcoder/bitmatrix.hpp"
• Link: https://drken1215.hatenablog.com/entry/2019/03/20/202800

概要

$\mathbb{F}_2$ 上での行列演算を std::bitset を用いて高速に行う.

行列のランクを求めたり, 連立一次方程式を解いたりするときに使う.

• BitMatrix(H,W) : $H$ 行 $W$ 列の行列を作る. 初期値は 0.
• GaussJordan(A) : 行列 $A$ のランクを求める.
• LinearEquation(A, b, x) : $Ax = b$ の解 $x$ を一つ見つけて x に書き込み, $A$ のランクを返す. 解がない場合は -1 を返す.

計算量

• BitMatrix(H,W) : $O(HW/64)$
• GaussJordan(A) : $H \times W$ 行列 $A$ に対して $O(\min(H,W)HW/64)$.
• LinearEquation(A, b, x) : $H \times W$ 行列 $A$ に対して $O(\min(H,W)HW/64)$.

Verified with

• test/bitmatrix.test.cpp

Code

#ifndef ATCODER_BITMATRIX_HPP
#define ATCODER_BITMATRIX_HPP 1

#include <bitset>
#include <iostream>
#include <vector>

namespace atcoder {

// https://drken1215.hatenablog.com/entry/2019/03/20/202800
template<int MAX_ROW = 510, int MAX_COL = 510>
struct BitMatrix {
    int H, W;
    std::bitset<MAX_COL> val[MAX_ROW];
    BitMatrix(int h, int w) : H(h), W(w) {}
    const std::bitset<MAX_COL>& operator[](int i) const { return val[i]; }
    std::bitset<MAX_COL>& operator[](int i) { return val[i]; }
};

template<int MAX_ROW = 510, int MAX_COL = 510>
std::ostream& operator<<(std::ostream& os, BitMatrix<MAX_ROW, MAX_COL>& A) {
    os << std::endl;
    for (int i = 0; i < A.H; ++i) {
        for (int j = 0; j < A.W; ++j) {
            os << A[i][j] << ", ";
        }
        os << std::endl;
    }
    return os;
}

template<int MAX_ROW = 510, int MAX_COL = 510>
int GaussJordan(BitMatrix<MAX_ROW, MAX_COL> &A, bool is_extended = false) {
    int rank = 0;
    for (int col = 0; col < A.W; ++col) {
        if (is_extended && col == A.W - 1) break;
        int pivot = -1;
        for (int row = rank; row < A.H; ++row) {
            if (A[row][col]) {
                pivot = row;
                break;
            }
        }
        if (pivot == -1) continue;
        swap(A[pivot], A[rank]);
        for (int row = 0; row < A.H; ++row) {
            if (row != rank && A[row][col]) A[row] ^= A[rank];
        }
        ++rank;
    }
    return rank;
}

template<int MAX_ROW = 510, int MAX_COL = 510>
int LinearEquation(const BitMatrix<MAX_ROW, MAX_COL>& A, const std::vector<bool>& b, std::vector<bool> &x) {
    int m = A.H, n = A.W;
    BitMatrix<MAX_ROW,MAX_COL> M(m, n + 1);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) M[i][j] = A[i][j];
        M[i][n] = b[i];
    }
    int rank = GaussJordan(M, true);

    // check if it has no solution
    for (int row = rank; row < m; ++row) if (M[row][n]) return -1;

    // answer
    x.assign(n, false);
    for (int row = 0, col = 0; row < rank; ++row) {
        while (M[row][col] == 0) ++col;
        x[col] = M[row][n];
    }
    return rank;
}

}  // namespace atcoder

#endif  // ATCODER_BITMATRIX_HPP

#line 1 "atcoder/bitmatrix.hpp"



#include <bitset>
#include <iostream>
#include <vector>

namespace atcoder {

// https://drken1215.hatenablog.com/entry/2019/03/20/202800
template<int MAX_ROW = 510, int MAX_COL = 510>
struct BitMatrix {
    int H, W;
    std::bitset<MAX_COL> val[MAX_ROW];
    BitMatrix(int h, int w) : H(h), W(w) {}
    const std::bitset<MAX_COL>& operator[](int i) const { return val[i]; }
    std::bitset<MAX_COL>& operator[](int i) { return val[i]; }
};

template<int MAX_ROW = 510, int MAX_COL = 510>
std::ostream& operator<<(std::ostream& os, BitMatrix<MAX_ROW, MAX_COL>& A) {
    os << std::endl;
    for (int i = 0; i < A.H; ++i) {
        for (int j = 0; j < A.W; ++j) {
            os << A[i][j] << ", ";
        }
        os << std::endl;
    }
    return os;
}

template<int MAX_ROW = 510, int MAX_COL = 510>
int GaussJordan(BitMatrix<MAX_ROW, MAX_COL> &A, bool is_extended = false) {
    int rank = 0;
    for (int col = 0; col < A.W; ++col) {
        if (is_extended && col == A.W - 1) break;
        int pivot = -1;
        for (int row = rank; row < A.H; ++row) {
            if (A[row][col]) {
                pivot = row;
                break;
            }
        }
        if (pivot == -1) continue;
        swap(A[pivot], A[rank]);
        for (int row = 0; row < A.H; ++row) {
            if (row != rank && A[row][col]) A[row] ^= A[rank];
        }
        ++rank;
    }
    return rank;
}

template<int MAX_ROW = 510, int MAX_COL = 510>
int LinearEquation(const BitMatrix<MAX_ROW, MAX_COL>& A, const std::vector<bool>& b, std::vector<bool> &x) {
    int m = A.H, n = A.W;
    BitMatrix<MAX_ROW,MAX_COL> M(m, n + 1);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) M[i][j] = A[i][j];
        M[i][n] = b[i];
    }
    int rank = GaussJordan(M, true);

    // check if it has no solution
    for (int row = rank; row < m; ++row) if (M[row][n]) return -1;

    // answer
    x.assign(n, false);
    for (int row = 0, col = 0; row < rank; ++row) {
        while (M[row][col] == 0) ++col;
        x[col] = M[row][n];
    }
    return rank;
}

}  // namespace atcoder

Back to top page