Monoid Power
(monoid/power.hpp)

• View this file on GitHub
• Last update: 2026-07-16 20:44:42+09:00
• Include: #include "monoid/power.hpp"

Overview

A utility function that computes the $n$-th power of an element $a$ in a generic Monoid using binary exponentiation. It operates in $O(\log n)$ time. This is highly useful for fast matrix exponentiation, string repetition, or finding the $n$-th composition of a function.

Template Parameters

• M: A struct representing the mathematical monoid, satisfying the m1une::monoid::IsMonoid concept.

Parameters

• typename M::value_type a: The base element.
• long long n: The exponent (number of times to apply the operation).

Example

#include "monoid/power.hpp"
#include "monoid/matrix.hpp"
#include <iostream>

using Mat = m1une::monoid::Matrix<long long, 2>;

int main() {
    Mat::value_type transition{};
    transition[0] = {1, 1};
    transition[1] = {1, 0};

    // Compute the 10th power of the Fibonacci transition matrix
    auto res = m1une::monoid::power<Mat>(transition, 10);

    std::cout << res[0][0] << "\n";
    return 0;
}

Interface and Complexity

This is a stateless algebra tag. Generic data structures use its public value_type, id(), and op(a, b) members. If the type also provides helpers such as make(...) or inv(x), they are described above or in the documented properties.

Each static operation runs in the cost of the underlying operation shown in the properties. Scalar monoids are $O(1)$; monoids whose value_type stores several items, permutations, or matrices scale with that stored size.

Depends on

• Monoid Concept (monoid/concept.hpp)

Required by

• Range Update Range Product (acted_monoid/range_update_range_product.hpp)

Verified with

• verify/ds/segtree/range_update_range_product.test.cpp
• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_MONOID_POWER_HPP
#define M1UNE_MONOID_POWER_HPP 1

#include "concept.hpp"

namespace m1une {
namespace monoid {

// Computes a^n (a * a * ... * a, n times) for an element 'a' in Monoid 'M'.
// Uses binary exponentiation to achieve O(log n) time complexity.
// The template parameter 'M' is constrained by the 'IsMonoid' concept.
template <IsMonoid M>
constexpr typename M::value_type power(typename M::value_type a, long long n) {
    typename M::value_type res = M::id();
    while (n > 0) {
        if (n & 1) {
            res = M::op(res, a);
        }
        a = M::op(a, a);
        n >>= 1;
    }
    return res;
}

}  // namespace monoid
}  // namespace m1une

#endif  // M1UNE_MONOID_POWER_HPP

#line 1 "monoid/power.hpp"



#line 1 "monoid/concept.hpp"



#include <concepts>

namespace m1une {
namespace monoid {

// Concept to check if a type satisfies the requirements of a Monoid.
// A Monoid must have a `value_type`, an identity element `id()`, and an associative binary operation `op()`.
template <typename M>
concept IsMonoid = requires(typename M::value_type a, typename M::value_type b) {
    // 1. Must define `value_type`
    typename M::value_type;

    // 2. Must have a static method `id()` returning `value_type`
    { M::id() } -> std::same_as<typename M::value_type>;

    // 3. Must have a static method `op(a, b)` returning `value_type`
    { M::op(a, b) } -> std::same_as<typename M::value_type>;
};

// Concept for groups. A type satisfying this concept must also obey the group
// laws; concepts can check the interface but not the algebraic properties.
template <typename M>
concept IsGroup = IsMonoid<M> && requires(typename M::value_type a) {
    { M::inv(a) } -> std::same_as<typename M::value_type>;
};

// Concept for commutative groups. Commutativity is a semantic requirement and
// cannot be checked by a C++ concept.
template <typename M>
concept IsCommutativeGroup = IsGroup<M>;

}  // namespace monoid
}  // namespace m1une


#line 5 "monoid/power.hpp"

namespace m1une {
namespace monoid {

// Computes a^n (a * a * ... * a, n times) for an element 'a' in Monoid 'M'.
// Uses binary exponentiation to achieve O(log n) time complexity.
// The template parameter 'M' is constrained by the 'IsMonoid' concept.
template <IsMonoid M>
constexpr typename M::value_type power(typename M::value_type a, long long n) {
    typename M::value_type res = M::id();
    while (n > 0) {
        if (n & 1) {
            res = M::op(res, a);
        }
        a = M::op(a, a);
        n >>= 1;
    }
    return res;
}

}  // namespace monoid
}  // namespace m1une

Back to top page