Range multiply / Range product
(Mylib/AlgebraicStructure/MonoidAction/multiply_product.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

Requirements

Notes

Problems

References

Depends on

• Binary exponentiation (Mylib/Number/pow.cpp)

Code

#pragma once
#include "Mylib/Number/pow.cpp"

namespace haar_lib {
  template <typename MonoidUpdate, typename MonoidGet>
  struct multiply_product {
    using monoid_get        = MonoidGet;
    using monoid_update     = MonoidUpdate;
    using value_type_get    = typename MonoidGet::value_type;
    using value_type_update = typename MonoidUpdate::value_type;

    value_type_get operator()(value_type_get a, value_type_update b, int len) const {
      return a * pow<MonoidUpdate>(b, len);
    }
  };
}  // namespace haar_lib

#line 2 "Mylib/Number/pow.cpp"
#include <cassert>
#include <cstdint>

namespace haar_lib {
  template <typename Monoid, typename value_type = typename Monoid::value_type>
  value_type pow(value_type a, int64_t p) {
    assert(p >= 0);
    const Monoid M;
    auto ret = M();

    while (p > 0) {
      if (p & 1) ret = M(ret, a);
      a = M(a, a);
      p >>= 1;
    }

    return ret;
  }
}  // namespace haar_lib
#line 3 "Mylib/AlgebraicStructure/MonoidAction/multiply_product.cpp"

namespace haar_lib {
  template <typename MonoidUpdate, typename MonoidGet>
  struct multiply_product {
    using monoid_get        = MonoidGet;
    using monoid_update     = MonoidUpdate;
    using value_type_get    = typename MonoidGet::value_type;
    using value_type_update = typename MonoidUpdate::value_type;

    value_type_get operator()(value_type_get a, value_type_update b, int len) const {
      return a * pow<MonoidUpdate>(b, len);
    }
  };
}  // namespace haar_lib

Back to top page