This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub maspypy/library
#include "alg/acted_monoid/sum_affine.hpp"
#include "alg/monoid/add.hpp" #include "alg/monoid/affine.hpp" template <typename E> struct ActedMonoid_Sum_Affine { using Monoid_X = Monoid_Add<E>; using Monoid_A = Monoid_Affine<E>; using X = typename Monoid_X::value_type; using A = typename Monoid_A::value_type; static constexpr X act(const X &x, const A &a, const ll &size) { return x * a.fi + E(size) * a.se; } };
#line 2 "alg/monoid/add.hpp" template <typename E> struct Monoid_Add { using X = E; using value_type = X; static constexpr X op(const X &x, const X &y) noexcept { return x + y; } static constexpr X inverse(const X &x) noexcept { return -x; } static constexpr X power(const X &x, ll n) noexcept { return X(n) * x; } static constexpr X unit() { return X(0); } static constexpr bool commute = true; }; #line 2 "alg/monoid/affine.hpp" // op(F, G) = comp(G,F), F のあとで G template <typename K> struct Monoid_Affine { using F = pair<K, K>; using value_type = F; using X = value_type; static constexpr F op(const F &x, const F &y) noexcept { return F({x.first * y.first, x.second * y.first + y.second}); } static constexpr F inverse(const F &x) { auto [a, b] = x; a = K(1) / a; return {a, a * (-b)}; } static constexpr K eval(const F &f, K x) noexcept { return f.first * x + f.second; } static constexpr F unit() { return {K(1), K(0)}; } static constexpr bool commute = false; }; #line 3 "alg/acted_monoid/sum_affine.hpp" template <typename E> struct ActedMonoid_Sum_Affine { using Monoid_X = Monoid_Add<E>; using Monoid_A = Monoid_Affine<E>; using X = typename Monoid_X::value_type; using A = typename Monoid_A::value_type; static constexpr X act(const X &x, const A &a, const ll &size) { return x * a.fi + E(size) * a.se; } };