algebra/monoid_f/monoid_affine.hpp

• View this file on GitHub
• Last update: 2024-03-24 17:04:51+09:00
• Include: #include "algebra/monoid_f/monoid_affine.hpp"

Required by

• algebra/monoid_s_f/monoid_sum_size_affine.hpp

Verified with

• verify/lc_data_structure/lc_range_affine_range_sum.test.cpp

Code

#pragma once
// MF
template <class T> struct MonoidAffine {
    using F = std::pair<T, T>;  // a * x + b -> {a, b}
    // f(x) = f.first * x + f.second, g(x) = g.first * x + g.second
    // f(g(x)) = f.first * (g.first * x + g.second) + f.second
    //         = f.first * g.first * x + f.first * g.second + f.second
    static constexpr F composition(F f, F g) { return {f.first * g.first, f.first * g.second + f.second}; }
    static constexpr F id() { return {T(1), T(0)}; }
};

#line 2 "algebra/monoid_f/monoid_affine.hpp"
// MF
template <class T> struct MonoidAffine {
    using F = std::pair<T, T>;  // a * x + b -> {a, b}
    // f(x) = f.first * x + f.second, g(x) = g.first * x + g.second
    // f(g(x)) = f.first * (g.first * x + g.second) + f.second
    //         = f.first * g.first * x + f.first * g.second + f.second
    static constexpr F composition(F f, F g) { return {f.first * g.first, f.first * g.second + f.second}; }
    static constexpr F id() { return {T(1), T(0)}; }
};

Back to top page