library

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

View the Project on GitHub gyouzasushi/library

:heavy_check_mark: test/unit/matrix.test.cpp

Depends on

Code

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

#include "algebra/semiring_max_plus.hpp"
#include "algebra/semiring_min_plus.hpp"
#include "math/matrix.hpp"
using mint = atcoder::modint998244353;
int main() {
    std::mt19937 rng(7959);
    for (int trial = 0; trial < 50; trial++) {
        int n = 1 + rng() % 5, m = 1 + rng() % 5, k = 1 + rng() % 5;
        matrix<mint> a(n, m), b(m, k), c(n, m);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) a[i][j] = rng(), c[i][j] = rng();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < k; j++) b[i][j] = rng();
        auto ab = a * b;
        assert(ab.height() == n && ab.width() == k);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < k; j++) {
                mint s = 0;
                for (int l = 0; l < m; l++) s += a[i][l] * b[l][j];
                assert(ab[i][j] == s);
            }
        }
        auto ac = a + c;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) assert(ac[i][j] == a[i][j] + c[i][j]);
        auto d = a;
        d += c;
        assert(d == ac);
        matrix<mint> sq(n, n);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) sq[i][j] = rng() % 3;
        int e = rng() % 6;
        auto naive = matrix<mint>::e(n);
        for (int t = 0; t < e; t++) naive *= sq;
        assert(sq.pow(e) == naive);
        assert(sq * matrix<mint>::e(n) == sq);
    }
    for (int trial = 0; trial < 50; trial++) {
        using R = semiring_min_plus<long long>;
        const long long inf = R::zero();
        int n = 1 + rng() % 5;
        semiring_matrix<R> g(n, n);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (rng() % 2) g[i][j] = rng() % 10;
        int k = rng() % 6;
        std::vector<std::vector<long long>> dp(n, std::vector<long long>(n, inf));
        for (int i = 0; i < n; i++) dp[i][i] = 0;
        for (int t = 0; t < k; t++) {
            std::vector<std::vector<long long>> nx(n, std::vector<long long>(n, inf));
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (dp[i][j] != inf)
                        for (int l = 0; l < n; l++)
                            if (g[j][l] != inf) nx[i][l] = std::min(nx[i][l], dp[i][j] + g[j][l]);
            dp = nx;
        }
        assert(g.pow(k) == semiring_matrix<R>(dp));
    }
    {
        using R = semiring_max_plus<long long>;
        semiring_matrix<R> g(std::vector<std::vector<long long>>{{R::zero(), 3}, {5, R::zero()}});
        auto g2 = g * g;
        assert(g2[0][0] == 8 && g2[1][1] == 8 && g2[0][1] == R::zero());
        assert(semiring_matrix<R>::e(2)[0][1] == R::zero() && semiring_matrix<R>::e(2)[0][0] == 0);
    }
    {
        matrix<int> z;
        assert(z.height() == 0 && z.width() == 0);
        assert(matrix<int>(0, 0).pow(5) == matrix<int>());
    }
    std::cout << "Hello World" << std::endl;
    return 0;
}
#line 1 "test/unit/matrix.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <atcoder/modint>
#include <cassert>
#include <iostream>
#include <limits>
#include <random>
#include <vector>

#line 2 "algebra/semiring_max_plus.hpp"
#include <algorithm>
#line 4 "algebra/semiring_max_plus.hpp"
template <class T>
struct semiring_max_plus {
    using S = T;
    static S add(S a, S b) {
        return std::max(a, b);
    }
    static S zero() {
        return std::numeric_limits<T>::lowest();
    }
    static S mul(S a, S b) {
        if (a == zero() || b == zero()) return zero();
        return a + b;
    }
    static S one() {
        return T(0);
    }
};
#line 4 "algebra/semiring_min_plus.hpp"
template <class T>
struct semiring_min_plus {
    using S = T;
    static S add(S a, S b) {
        return std::min(a, b);
    }
    static S zero() {
        return std::numeric_limits<T>::max();
    }
    static S mul(S a, S b) {
        if (a == zero() || b == zero()) return zero();
        return a + b;
    }
    static S one() {
        return T(0);
    }
};
#line 3 "math/matrix.hpp"
#include <utility>
#line 5 "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>;
};
#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 8 "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>>;
#line 12 "test/unit/matrix.test.cpp"
using mint = atcoder::modint998244353;
int main() {
    std::mt19937 rng(7959);
    for (int trial = 0; trial < 50; trial++) {
        int n = 1 + rng() % 5, m = 1 + rng() % 5, k = 1 + rng() % 5;
        matrix<mint> a(n, m), b(m, k), c(n, m);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) a[i][j] = rng(), c[i][j] = rng();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < k; j++) b[i][j] = rng();
        auto ab = a * b;
        assert(ab.height() == n && ab.width() == k);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < k; j++) {
                mint s = 0;
                for (int l = 0; l < m; l++) s += a[i][l] * b[l][j];
                assert(ab[i][j] == s);
            }
        }
        auto ac = a + c;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) assert(ac[i][j] == a[i][j] + c[i][j]);
        auto d = a;
        d += c;
        assert(d == ac);
        matrix<mint> sq(n, n);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) sq[i][j] = rng() % 3;
        int e = rng() % 6;
        auto naive = matrix<mint>::e(n);
        for (int t = 0; t < e; t++) naive *= sq;
        assert(sq.pow(e) == naive);
        assert(sq * matrix<mint>::e(n) == sq);
    }
    for (int trial = 0; trial < 50; trial++) {
        using R = semiring_min_plus<long long>;
        const long long inf = R::zero();
        int n = 1 + rng() % 5;
        semiring_matrix<R> g(n, n);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (rng() % 2) g[i][j] = rng() % 10;
        int k = rng() % 6;
        std::vector<std::vector<long long>> dp(n, std::vector<long long>(n, inf));
        for (int i = 0; i < n; i++) dp[i][i] = 0;
        for (int t = 0; t < k; t++) {
            std::vector<std::vector<long long>> nx(n, std::vector<long long>(n, inf));
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (dp[i][j] != inf)
                        for (int l = 0; l < n; l++)
                            if (g[j][l] != inf) nx[i][l] = std::min(nx[i][l], dp[i][j] + g[j][l]);
            dp = nx;
        }
        assert(g.pow(k) == semiring_matrix<R>(dp));
    }
    {
        using R = semiring_max_plus<long long>;
        semiring_matrix<R> g(std::vector<std::vector<long long>>{{R::zero(), 3}, {5, R::zero()}});
        auto g2 = g * g;
        assert(g2[0][0] == 8 && g2[1][1] == 8 && g2[0][1] == R::zero());
        assert(semiring_matrix<R>::e(2)[0][1] == R::zero() && semiring_matrix<R>::e(2)[0][0] == 0);
    }
    {
        matrix<int> z;
        assert(z.height() == 0 && z.width() == 0);
        assert(matrix<int>(0, 0).pow(5) == matrix<int>());
    }
    std::cout << "Hello World" << std::endl;
    return 0;
}
Back to top page