alg/monoid_pow.hpp

• View this file on GitHub
• Last update: 2023-11-23 14:15:12+09:00
• Include: #include "alg/monoid_pow.hpp"

Required by

• mod/floor_monoid_product.hpp
• mod/floor_sum_of_linear_polynomial.hpp

Verified with

• test/library_checker/math/sum_of_floor_of_linear_2.test.cpp
• test/mytest/floor_sum_of_polynomial.test.cpp
• test/yukicoder/2362.test.cpp
• test_atcoder/abc200f.test.cpp

Code

#pragma once

template <typename Monoid>
typename Monoid::X monoid_pow(typename Monoid::X x, u64 exp) {
  using X = typename Monoid::X;
  assert(exp >= 0);
  X res = Monoid::unit();
  while (exp) {
    if (exp & 1) res = Monoid::op(res, x);
    x = Monoid::op(x, x);
    exp >>= 1;
  }
  return res;
}

#line 2 "alg/monoid_pow.hpp"

template <typename Monoid>
typename Monoid::X monoid_pow(typename Monoid::X x, u64 exp) {
  using X = typename Monoid::X;
  assert(exp >= 0);
  X res = Monoid::unit();
  while (exp) {
    if (exp & 1) res = Monoid::op(res, x);
    x = Monoid::op(x, x);
    exp >>= 1;
  }
  return res;
}

Back to top page