library

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

View the Project on GitHub gyouzasushi/library

:heavy_check_mark: test/unit/linear_algebra.test.cpp

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <atcoder/modint>
#include <cassert>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

#include "math/matrix.hpp"
using mint = atcoder::modint998244353;
mint det_brute(const matrix<mint>& a) {
    int n = a.height();
    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 0);
    mint ret = 0;
    do {
        mint term = 1;
        for (int i = 0; i < n; i++) term *= a[i][p[i]];
        int inv = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) inv += p[i] > p[j];
        ret += inv & 1 ? -term : term;
    } while (std::next_permutation(p.begin(), p.end()));
    return ret;
}
// rank = largest k with a nonsingular k x k minor
int rank_brute(const matrix<mint>& a) {
    int h = a.height(), w = a.width();
    for (int k = std::min(h, w); k >= 1; k--) {
        for (int rs = 0; rs < (1 << h); rs++) {
            if (__builtin_popcount(rs) != k) continue;
            for (int cs = 0; cs < (1 << w); cs++) {
                if (__builtin_popcount(cs) != k) continue;
                matrix<mint> m(k, k);
                int i = 0;
                for (int r = 0; r < h; r++) {
                    if (!(rs >> r & 1)) continue;
                    int j = 0;
                    for (int c = 0; c < w; c++) {
                        if (cs >> c & 1) m[i][j++] = a[r][c];
                    }
                    i++;
                }
                if (det_brute(m) != 0) return k;
            }
        }
    }
    return 0;
}
std::vector<mint> mul(const matrix<mint>& a, const std::vector<mint>& x) {
    std::vector<mint> y(a.height());
    for (int i = 0; i < a.height(); i++)
        for (int j = 0; j < a.width(); j++) y[i] += a[i][j] * x[j];
    return y;
}
int main() {
    std::mt19937 rng(2026);
    auto rnd = [&](int h, int w, int small) {
        matrix<mint> a(h, w);
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++) a[i][j] = small ? int(rng() % 3) : int(rng());
        return a;
    };
    for (int it = 0; it < 300; it++) {
        int n = rng() % 6;
        matrix<mint> a = rnd(n, n, rng() % 2);
        mint d = determinant(a);
        assert(d == det_brute(a));
        auto inv = inverse(a);
        assert(inv.has_value() == (d != 0));
        if (inv) {
            assert(a * *inv == matrix<mint>::e(n));
            assert(*inv * a == matrix<mint>::e(n));
            assert(determinant(*inv) * d == 1);
        }
        assert(matrix_rank(a) == rank_brute(a));
    }
    for (int it = 0; it < 300; it++) {
        int h = rng() % 5, w = rng() % 5;
        matrix<mint> a = rnd(h, w, rng() % 2);
        assert(matrix_rank(a) == rank_brute(a));
        std::vector<mint> b(h);
        bool consistent = rng() % 2;
        if (consistent) {
            std::vector<mint> x0(w);
            for (auto& v : x0) v = int(rng() % 5);
            b = mul(a, x0);
        } else {
            for (auto& v : b) v = int(rng() % 3);
        }
        auto s = solve_linear_system(a, b);
        if (consistent) assert(s.has_value());
        if (!s) {
            // b not in column space: rank of [a | b] exceeds rank of a
            matrix<mint> ab(h, w + 1);
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) ab[i][j] = a[i][j];
                ab[i][w] = b[i];
            }
            assert(matrix_rank(ab) == matrix_rank(a) + 1);
            continue;
        }
        int r = matrix_rank(a);
        assert(int(s->kernel.size()) == w - r);
        assert(mul(a, s->x) == b);
        matrix<mint> k(int(s->kernel.size()), w);
        for (int i = 0; i < int(s->kernel.size()); i++) {
            assert(mul(a, s->kernel[i]) == std::vector<mint>(h));
            k[i] = s->kernel[i];
        }
        assert(matrix_rank(k) == int(s->kernel.size()));
    }
    {
        // 0 x 0
        matrix<mint> z(0, 0);
        assert(determinant(z) == 1 && inverse(z).has_value() && matrix_rank(z) == 0);
        auto s = solve_linear_system(z, {});
        assert(s && s->x.empty() && s->kernel.empty());
        // 500 x 500 timing
        matrix<mint> a = rnd(500, 500, 0);
        determinant(a);
        inverse(a);
        matrix_rank(a);
        solve_linear_system(a, std::vector<mint>(500, 1));
    }
    std::cout << "Hello World" << std::endl;
}
#line 1 "test/unit/linear_algebra.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <atcoder/modint>
#include <cassert>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

#line 3 "math/matrix.hpp"
#include <optional>
#include <utility>
#line 6 "math/matrix.hpp"

#line 2 "algebra/concept.hpp"
#include <concepts>
template <class M>
concept semigroup = requires(typename M::S a, typename M::S b) {
    { M::op(a, b) } -> std::same_as<typename M::S>;
};
template <class M>
concept monoid = semigroup<M> && requires {
    { M::e() } -> std::same_as<typename M::S>;
};
template <class G>
concept group = monoid<G> && requires(typename G::S a) {
    { G::inv(a) } -> std::same_as<typename G::S>;
};
template <class A>
concept action = requires(typename A::F f, typename A::F g) {
    { A::composition(f, g) } -> std::same_as<typename A::F>;
    { A::id() } -> std::same_as<typename A::F>;
    { A::composition_commutative } -> std::convertible_to<bool>;
};
template <class A>
concept acted_monoid = monoid<A> && action<A> && requires(typename A::S x, typename A::F f) {
    { A::mapping(f, x) } -> std::same_as<typename A::S>;
};
template <class R>
concept semiring = requires(typename R::S a, typename R::S b) {
    { R::add(a, b) } -> std::same_as<typename R::S>;
    { R::zero() } -> std::same_as<typename R::S>;
    { R::mul(a, b) } -> std::same_as<typename R::S>;
    { R::one() } -> std::same_as<typename R::S>;
};
template <class A>
concept beats_acted_monoid = acted_monoid<A> && requires(typename A::S x) {
    { x.fail } -> std::convertible_to<bool>;
};
#line 2 "algebra/semiring_plus_times.hpp"
template <class T>
struct semiring_plus_times {
    using S = T;
    static S add(S a, S b) {
        return a + b;
    }
    static S zero() {
        return T(0);
    }
    static S mul(S a, S b) {
        return a * b;
    }
    static S one() {
        return T(1);
    }
};
#line 9 "math/matrix.hpp"
template <semiring R>
struct semiring_matrix {
    using S = typename R::S;
    semiring_matrix() : semiring_matrix(0, 0) {}
    semiring_matrix(int h, int w) : h(h), w(w), a(h, std::vector<S>(w, R::zero())) {}
    explicit semiring_matrix(std::vector<std::vector<S>> v) : h(int(v.size())), w(h ? int(v[0].size()) : 0), a(std::move(v)) {
        for (int i = 0; i < h; i++) assert(int(a[i].size()) == w);
    }
    static semiring_matrix e(int n) {
        semiring_matrix ret(n, n);
        for (int i = 0; i < n; i++) ret[i][i] = R::one();
        return ret;
    }
    int height() const {
        return h;
    }
    int width() const {
        return w;
    }
    const std::vector<S>& operator[](int i) const {
        return a[i];
    }
    std::vector<S>& operator[](int i) {
        return a[i];
    }
    friend semiring_matrix operator+(const semiring_matrix& lhs, const semiring_matrix& rhs) {
        assert(lhs.h == rhs.h && lhs.w == rhs.w);
        semiring_matrix ret(lhs.h, lhs.w);
        for (int i = 0; i < lhs.h; i++) {
            for (int j = 0; j < lhs.w; j++) ret[i][j] = R::add(lhs[i][j], rhs[i][j]);
        }
        return ret;
    }
    friend semiring_matrix operator*(const semiring_matrix& lhs, const semiring_matrix& rhs) {
        assert(lhs.w == rhs.h);
        semiring_matrix ret(lhs.h, rhs.w);
        for (int i = 0; i < lhs.h; i++) {
            for (int k = 0; k < lhs.w; k++) {
                for (int j = 0; j < rhs.w; j++) ret[i][j] = R::add(ret[i][j], R::mul(lhs[i][k], rhs[k][j]));
            }
        }
        return ret;
    }
    semiring_matrix& operator+=(const semiring_matrix& rhs) {
        return *this = *this + rhs;
    }
    semiring_matrix& operator*=(const semiring_matrix& rhs) {
        return *this = *this * rhs;
    }
    semiring_matrix pow(long long k) const {
        assert(h == w && k >= 0);
        semiring_matrix x = *this, ret = e(h);
        while (k) {
            if (k & 1) ret *= x;
            x *= x;
            k >>= 1;
        }
        return ret;
    }
    friend bool operator==(const semiring_matrix& lhs, const semiring_matrix& rhs) {
        return lhs.a == rhs.a;
    }

private:
    int h, w;
    std::vector<std::vector<S>> a;
};
template <class T>
using matrix = semiring_matrix<semiring_plus_times<T>>;
template <class T> T determinant(matrix<T> a) {
    int n = a.height();
    assert(n == a.width());
    T det = 1;
    for (int c = 0; c < n; c++) {
        int p = c;
        while (p < n && a[p][c] == T(0)) p++;
        if (p == n) return 0;
        if (p != c) {
            std::swap(a[p], a[c]);
            det = -det;
        }
        det *= a[c][c];
        T inv = T(1) / a[c][c];
        for (int i = c + 1; i < n; i++) {
            if (a[i][c] == T(0)) continue;
            T f = a[i][c] * inv;
            for (int j = c; j < n; j++) a[i][j] -= f * a[c][j];
        }
    }
    return det;
}
template <class T> std::optional<matrix<T>> inverse(matrix<T> a) {
    int n = a.height();
    assert(n == a.width());
    matrix<T> b = matrix<T>::e(n);
    for (int c = 0; c < n; c++) {
        int p = c;
        while (p < n && a[p][c] == T(0)) p++;
        if (p == n) return std::nullopt;
        std::swap(a[p], a[c]);
        std::swap(b[p], b[c]);
        T inv = T(1) / a[c][c];
        for (int j = 0; j < n; j++) {
            a[c][j] *= inv;
            b[c][j] *= inv;
        }
        for (int i = 0; i < n; i++) {
            if (i == c || a[i][c] == T(0)) continue;
            T f = a[i][c];
            for (int j = 0; j < n; j++) {
                a[i][j] -= f * a[c][j];
                b[i][j] -= f * b[c][j];
            }
        }
    }
    return b;
}
template <class T> int matrix_rank(matrix<T> a) {
    int h = a.height(), w = a.width(), r = 0;
    for (int c = 0; c < w && r < h; c++) {
        int p = r;
        while (p < h && a[p][c] == T(0)) p++;
        if (p == h) continue;
        std::swap(a[p], a[r]);
        T inv = T(1) / a[r][c];
        for (int i = r + 1; i < h; i++) {
            if (a[i][c] == T(0)) continue;
            T f = a[i][c] * inv;
            for (int j = c; j < w; j++) a[i][j] -= f * a[r][j];
        }
        r++;
    }
    return r;
}
template <class T> struct linear_system_solution {
    std::vector<T> x;
    std::vector<std::vector<T>> kernel;
};
template <class T> std::optional<linear_system_solution<T>> solve_linear_system(matrix<T> a, std::vector<T> b) {
    int h = a.height(), w = a.width();
    assert(int(b.size()) == h);
    std::vector<int> pivot;
    int r = 0;
    for (int c = 0; c < w && r < h; c++) {
        int p = r;
        while (p < h && a[p][c] == T(0)) p++;
        if (p == h) continue;
        std::swap(a[p], a[r]);
        std::swap(b[p], b[r]);
        T inv = T(1) / a[r][c];
        for (int j = c; j < w; j++) a[r][j] *= inv;
        b[r] *= inv;
        for (int i = 0; i < h; i++) {
            if (i == r || a[i][c] == T(0)) continue;
            T f = a[i][c];
            for (int j = c; j < w; j++) a[i][j] -= f * a[r][j];
            b[i] -= f * b[r];
        }
        pivot.push_back(c);
        r++;
    }
    for (int i = r; i < h; i++) {
        if (b[i] != T(0)) return std::nullopt;
    }
    linear_system_solution<T> ret;
    ret.x.assign(w, T(0));
    for (int i = 0; i < r; i++) ret.x[pivot[i]] = b[i];
    std::vector<bool> is_pivot(w, false);
    for (int c : pivot) is_pivot[c] = true;
    for (int f = 0; f < w; f++) {
        if (is_pivot[f]) continue;
        std::vector<T> v(w, T(0));
        v[f] = T(1);
        for (int i = 0; i < r; i++) v[pivot[i]] = -a[i][f];
        ret.kernel.push_back(std::move(v));
    }
    return ret;
}
#line 11 "test/unit/linear_algebra.test.cpp"
using mint = atcoder::modint998244353;
mint det_brute(const matrix<mint>& a) {
    int n = a.height();
    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 0);
    mint ret = 0;
    do {
        mint term = 1;
        for (int i = 0; i < n; i++) term *= a[i][p[i]];
        int inv = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) inv += p[i] > p[j];
        ret += inv & 1 ? -term : term;
    } while (std::next_permutation(p.begin(), p.end()));
    return ret;
}
// rank = largest k with a nonsingular k x k minor
int rank_brute(const matrix<mint>& a) {
    int h = a.height(), w = a.width();
    for (int k = std::min(h, w); k >= 1; k--) {
        for (int rs = 0; rs < (1 << h); rs++) {
            if (__builtin_popcount(rs) != k) continue;
            for (int cs = 0; cs < (1 << w); cs++) {
                if (__builtin_popcount(cs) != k) continue;
                matrix<mint> m(k, k);
                int i = 0;
                for (int r = 0; r < h; r++) {
                    if (!(rs >> r & 1)) continue;
                    int j = 0;
                    for (int c = 0; c < w; c++) {
                        if (cs >> c & 1) m[i][j++] = a[r][c];
                    }
                    i++;
                }
                if (det_brute(m) != 0) return k;
            }
        }
    }
    return 0;
}
std::vector<mint> mul(const matrix<mint>& a, const std::vector<mint>& x) {
    std::vector<mint> y(a.height());
    for (int i = 0; i < a.height(); i++)
        for (int j = 0; j < a.width(); j++) y[i] += a[i][j] * x[j];
    return y;
}
int main() {
    std::mt19937 rng(2026);
    auto rnd = [&](int h, int w, int small) {
        matrix<mint> a(h, w);
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++) a[i][j] = small ? int(rng() % 3) : int(rng());
        return a;
    };
    for (int it = 0; it < 300; it++) {
        int n = rng() % 6;
        matrix<mint> a = rnd(n, n, rng() % 2);
        mint d = determinant(a);
        assert(d == det_brute(a));
        auto inv = inverse(a);
        assert(inv.has_value() == (d != 0));
        if (inv) {
            assert(a * *inv == matrix<mint>::e(n));
            assert(*inv * a == matrix<mint>::e(n));
            assert(determinant(*inv) * d == 1);
        }
        assert(matrix_rank(a) == rank_brute(a));
    }
    for (int it = 0; it < 300; it++) {
        int h = rng() % 5, w = rng() % 5;
        matrix<mint> a = rnd(h, w, rng() % 2);
        assert(matrix_rank(a) == rank_brute(a));
        std::vector<mint> b(h);
        bool consistent = rng() % 2;
        if (consistent) {
            std::vector<mint> x0(w);
            for (auto& v : x0) v = int(rng() % 5);
            b = mul(a, x0);
        } else {
            for (auto& v : b) v = int(rng() % 3);
        }
        auto s = solve_linear_system(a, b);
        if (consistent) assert(s.has_value());
        if (!s) {
            // b not in column space: rank of [a | b] exceeds rank of a
            matrix<mint> ab(h, w + 1);
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) ab[i][j] = a[i][j];
                ab[i][w] = b[i];
            }
            assert(matrix_rank(ab) == matrix_rank(a) + 1);
            continue;
        }
        int r = matrix_rank(a);
        assert(int(s->kernel.size()) == w - r);
        assert(mul(a, s->x) == b);
        matrix<mint> k(int(s->kernel.size()), w);
        for (int i = 0; i < int(s->kernel.size()); i++) {
            assert(mul(a, s->kernel[i]) == std::vector<mint>(h));
            k[i] = s->kernel[i];
        }
        assert(matrix_rank(k) == int(s->kernel.size()));
    }
    {
        // 0 x 0
        matrix<mint> z(0, 0);
        assert(determinant(z) == 1 && inverse(z).has_value() && matrix_rank(z) == 0);
        auto s = solve_linear_system(z, {});
        assert(s && s->x.empty() && s->kernel.empty());
        // 500 x 500 timing
        matrix<mint> a = rnd(500, 500, 0);
        determinant(a);
        inverse(a);
        matrix_rank(a);
        solve_linear_system(a, std::vector<mint>(500, 1));
    }
    std::cout << "Hello World" << std::endl;
}
Back to top page