alg/acted_monoid/sum_assign.hpp

• View this file on GitHub
• Last update: 2023-10-14 20:28:40+09:00
• Include: #include "alg/acted_monoid/sum_assign.hpp"

Depends on

• alg/monoid/add.hpp
• alg/monoid/assign.hpp

Verified with

• test/aoj/DSL_2_I.test.cpp
• test/yukicoder/2292.test.cpp
• test_atcoder/abc256ex.test.cpp
• test_atcoder/abc256ex2.test.cpp

Code

#include "alg/monoid/add.hpp"
#include "alg/monoid/assign.hpp"

template <typename E, E none_val>
struct ActedMonoid_Sum_Assign {
  using Monoid_X = Monoid_Add<E>;
  using Monoid_A = Monoid_Assign<E, none_val>;
  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) {
    if (a == Monoid_A::unit()) return x;
    return a * E(size);
  }
};

#line 2 "alg/monoid/add.hpp"

template <typename X>
struct Monoid_Add {
  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/assign.hpp"

template <typename X, int none_val>
struct Monoid_Assign {
  using value_type = X;
  static X op(X x, X y) { return (y == X(none_val) ? x : y); }
  static constexpr X unit() { return X(none_val); }
  static constexpr bool commute = false;
};
#line 3 "alg/acted_monoid/sum_assign.hpp"

template <typename E, E none_val>
struct ActedMonoid_Sum_Assign {
  using Monoid_X = Monoid_Add<E>;
  using Monoid_A = Monoid_Assign<E, none_val>;
  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) {
    if (a == Monoid_A::unit()) return x;
    return a * E(size);
  }
};

Back to top page