library

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

View the Project on GitHub kk2a/library

:warning: ベクトルが現在の基底と線形独立かどうかを判定する
(matrix/basis.hpp)

Depends on

Required by

Code

#ifndef KK2_MATRIX_BASIS_HPP
#define KK2_MATRIX_BASIS_HPP 1

#include <algorithm>
#include <cassert>
#include <optional>
#include <vector>

#include "matrix_field.hpp"

namespace kk2 {

namespace linear_algebra {

template <class Matrix, class Field> struct BasisBase {
    struct RowBasicTransform {
        int type;
        int i, j;
        Field t, t_inv;

        RowBasicTransform() = default;

        // type = 0: row(i) <- row(i) * t
        //           t_inv = 1 / t
        // type = 1: row(j) <- row(j) + row(i) * t
        //           t_inv = -t
        // type = 2: swap(row(i), row(j))
        //           t_inv = unused
        RowBasicTransform(int type_, int i_, int j_, Field t_, Field t_inv_)
            : type(type_),
              i(i_),
              j(j_),
              t(t_),
              t_inv(t_inv_) {}

        void transform(Matrix &mat, bool inv = false) const {
            if (type == 0) {
                if (inv) {
                    mat[i][0] *= t_inv;
                } else {
                    mat[i][0] *= t;
                }
            } else if (type == 1) {
                if (inv) {
                    mat[j][0] += mat[i][0] * t_inv;
                } else {
                    mat[j][0] += mat[i][0] * t;
                }
            } else if (type == 2) {
                std::swap(mat[i], mat[j]);
            }
        }
    };

    int h, rank;

    struct SnapShot {
        int rank, hist_size;
    };

    std::vector<RowBasicTransform> hist;
    std::vector<SnapShot> snaps;

    BasisBase() = default;

    BasisBase(int h_) : h(h_), rank(0) {}

    Matrix &sweep(Matrix &vec) const {
        for (auto &&t : hist) t.transform(vec);
        return vec;
    }

    /**
     * @brief ベクトルが現在の基底と線形独立かどうかを判定する
     * @param vec 列ベクトル
     * @return 線形独立ならtrue、そうでなければfalse
     */
    bool is_linearly_independent(const Matrix &vec) const {
        assert(vec.get_h() == h);
        assert(vec.get_w() == 1);
        if (rank == h) return false;

        Matrix tmp(vec);
        sweep(tmp);
        for (int i = rank; i < h; ++i) {
            if (tmp[i][0] != Field(0)) return true;
        }
        return false;
    }

    /**
     * @brief ベクトルを基底に追加する
     * @param vec 列ベクトル
     * @return
     * ベクトルが現在の基底と線形独立でない場合は座標ベクトルを返す、そうでなければnulloptを返す
     */
    std::optional<Matrix> add(const Matrix &vec) {
        assert(vec.get_h() == h);
        assert(vec.get_w() == 1);

        Matrix tmp(vec);
        sweep(tmp);

        int pivot = -1;
        for (int i = rank; i < h; ++i) {
            if (tmp[i][0] != Field(0)) {
                pivot = i;
                break;
            }
        }
        if (pivot == -1) return tmp;

        if (pivot != rank) {
            std::swap(tmp[pivot], tmp[rank]);
            hist.emplace_back(2, rank, pivot, Field(1), Field(1));
        }
        if (tmp[rank][0] != Field(1)) {
            hist.emplace_back(0, rank, -1, tmp[rank][0].inv(), tmp[rank][0]);
            tmp[rank][0] = Field(1);
        }
        for (int i = 0; i < h; ++i) {
            if (i == rank) continue;
            Field t = -tmp[i][0];
            if (t == Field(0)) continue;
            hist.emplace_back(1, rank, i, t, -t);
        }
        ++rank;
        return {};
    }

    Matrix get_coordinate(const Matrix &vec) const {
        assert(vec.get_h() == h);
        assert(vec.get_w() == 1);
        Matrix res(vec);
        sweep(res);
        for (int i = rank; i < h; ++i) assert(res[i][0] == Field(0));
        return res;
    }

    void snapshot() { snaps.emplace_back(rank, (int)hist.size()); }

    void rollback() {
        if (snaps.empty()) return;
        auto snap = snaps.back();
        snaps.pop_back();
        rank = snap.rank;
        hist.resize(snap.hist_size);
    }
};

} // namespace linear_algebra

template <class Matrix> using BasisMatrix =
    linear_algebra::BasisBase<Matrix, typename Matrix::value_type>;

} // namespace kk2

#endif // KK2_MATRIX_BASIS_HPP
Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 312, in update
    raise BundleErrorAt(path, i + 1, "#pragma once found in a non-first line")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: type_traits/io.hpp: line 4: #pragma once found in a non-first line
Back to top page