Concept for a type compatible with atcoder::static_modint (tools/modint_compatible.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-01-25 23:49:58+09:00
• Include: #include "tools/modint_compatible.hpp"

template <typename T>
concept modint_compatible = std::regular<T>
  && std::equality_comparable<T>
  && std::constructible_from<T, bool>
  && std::constructible_from<T, char>
  && std::constructible_from<T, int>
  && std::constructible_from<T, long long>
  && std::constructible_from<T, unsigned int>
  && std::constructible_from<T, unsigned long long>
  && requires(T a, T b, int v_int, long long v_ll) {
    { T::mod() } -> std::convertible_to<int>;
    { T::raw(v_int) } -> std::same_as<T>;
    { a.val() } -> std::convertible_to<int>;
    { ++a } -> std::same_as<T&>;
    { --a } -> std::same_as<T&>;
    { a++ } -> std::same_as<T>;
    { a-- } -> std::same_as<T>;
    { a += b } -> std::same_as<T&>;
    { a -= b } -> std::same_as<T&>;
    { a *= b } -> std::same_as<T&>;
    { a /= b } -> std::same_as<T&>;
    { +a } -> std::same_as<T>;
    { -a } -> std::same_as<T>;
    { a.pow(v_ll) } -> std::same_as<T>;
    { a.inv() } -> std::same_as<T>;
    { a + b } -> std::same_as<T>;
    { a - b } -> std::same_as<T>;
    { a * b } -> std::same_as<T>;
    { a / b } -> std::same_as<T>;
  };

It is a concept that represents a type compatible with atcoder::static_modint. For example, it accepts atcoder::dynamic_modint and tools::modint_for_rolling_hash.

Constraints

• None

Time Complexity

• Not applicable

License

• CC0

Author

• anqooqie

Required by

• Bell numbers (tools/bell.hpp)
• Berlekamp-Massey algorithm (tools/berlekamp_massey.hpp)
• Bernoulli numbers $B_k \pmod{P}$ for $0 \leq k \leq n$ (tools/bernoulli.hpp)
• $\prod_{i = 0}^{m - 1} (a_i + b_i x^{c_i})^{d_i}$ (tools/binomial_product.hpp)
• Bostan-Mori algorithm (tools/bostan_mori.hpp)
• Convolution (tools/convolution.hpp)
• tools/detail/rolling_hash.hpp
• List all divisors of a divisor of $n$ (tools/divisors_of_divisor.hpp)
• Extend operator>> (tools/extend_input.hpp)
• Extend operator<< (tools/extend_output.hpp)
• Cache for $n^{-1}, n!, n!^{-1} \pmod{P}$ (tools/fact_mod_cache.hpp)
• Formal Dirichlet series with prefix sums (tools/fds_with_prefix_sums.hpp)
• Formal power series (tools/fps.hpp)
• Precompute $n! \pmod{P}$ for $0 \leq n < P \approx 10^9$ (tools/large_fact_mod_cache.hpp)
• Concept for atcoder::static_modint and atcoder::dynamic_modint (tools/modint.hpp)
• $\mathbb{Z} / (2^{61} - 1) \mathbb{Z}$ (tools/modint_for_rolling_hash.hpp)
• Partition function (tools/partition_function.hpp)
• Polynomial (tools/polynomial.hpp)
• Polynomial interpolation (tools/polynomial_interpolation.hpp)
• Product of polynomials (tools/polynomial_product.hpp)
• Cache for $b^n \pmod{M}$ (tools/pow_mod_cache.hpp)
• Rolling hash (tools/rolling_hash.hpp)
• Shift of sampling points of polynomial (tools/sample_point_shift.hpp)
• Power of a sparse FPS (tools/sparse_fps_pow.hpp)
• Signed Stirling numbers of the first kind (tools/stirling_1st.hpp)
• Stirling numbers of the second kind (tools/stirling_2nd.hpp)
• Subset sum (tools/subset_sum.hpp)
• Twelvefold way (tools/twelvefold_way.hpp)
• Commonly used utilities for competitive programming (tools/util.hpp)
• Bitwise XOR convolution (tools/xor_convolution.hpp)

Verified with

• tests/bell/all.test.cpp
• tests/bell/consistent.test.cpp
• tests/bell/diagonal.test.cpp
• tests/bell/fixed_n.test.cpp
• tests/berlekamp_massey.test.cpp
• tests/bernoulli.test.cpp
• tests/bostan_mori.test.cpp
• tests/convolution/double.test.cpp
• tests/convolution/dynamic_mod.test.cpp
• tests/convolution/mod1000000007.test.cpp
• tests/convolution/mod998244353.test.cpp
• tests/divisors_of_divisor.test.cpp
• tests/extend_input.test.cpp
• tests/extend_output.test.cpp
• tests/fact_mod_cache.test.cpp
• tests/fds_with_prefix_sums/division.test.cpp
• tests/fds_with_prefix_sums/multiplication.test.cpp
• tests/fds_with_prefix_sums/sum_of_totient_function.test.cpp
• tests/fps/composition.test.cpp
• tests/fps/compositional_inverse.test.cpp
• tests/fps/exp_mod998244353.test.cpp
• tests/fps/exp_other_mods.test.cpp
• tests/fps/inv_mod998244353.test.cpp
• tests/fps/inv_other_mods.test.cpp
• tests/fps/log_mod998244353.test.cpp
• tests/fps/log_other_mods.test.cpp
• tests/fps/pow_mod998244353.test.cpp
• tests/fps/pow_other_mods.test.cpp
• tests/large_fact_mod_cache/binomial.test.cpp
• tests/large_fact_mod_cache/fact.test.cpp
• tests/modint.test.cpp
• tests/modint_compatible.test.cpp
• tests/multiplicative_structure.test.cpp
• tests/partition_function/all.test.cpp
• tests/partition_function/consistent.test.cpp
• tests/partition_function/diagonal.test.cpp
• tests/polynomial/extgcd.test.cpp
• tests/polynomial/multidimensional.test.cpp
• tests/polynomial/multipoint_evaluation.test.cpp
• tests/polynomial/multipoint_evaluation_other_mods.test.cpp
• tests/polynomial/naive_division.test.cpp
• tests/polynomial/ntt_division.test.cpp
• tests/polynomial/taylor_shift.test.cpp
• tests/polynomial_interpolation.test.cpp
• tests/polynomial_product.test.cpp
• tests/rolling_hash.test.cpp
• tests/sample_point_shift.test.cpp
• tests/sparse_fps_pow/fraction.test.cpp
• tests/sparse_fps_pow/regular.test.cpp
• tests/stirling_1st/consistent.test.cpp
• tests/stirling_1st/fixed_k.test.cpp
• tests/stirling_1st/fixed_n.test.cpp
• tests/stirling_2nd/all.test.cpp
• tests/stirling_2nd/consistent.test.cpp
• tests/stirling_2nd/fixed_k.test.cpp
• tests/stirling_2nd/fixed_n.test.cpp
• tests/subset_sum.test.cpp
• tests/twelvefold_way/labeled_ball_labeled_box_at_least_1.test.cpp
• tests/twelvefold_way/labeled_ball_labeled_box_at_most_1.test.cpp
• tests/twelvefold_way/labeled_ball_labeled_box_unrestricted.test.cpp
• tests/twelvefold_way/labeled_ball_unlabeled_box_at_least_1.test.cpp
• tests/twelvefold_way/labeled_ball_unlabeled_box_at_most_1.test.cpp
• tests/twelvefold_way/labeled_ball_unlabeled_box_unrestricted.test.cpp
• tests/twelvefold_way/unlabeled_ball_labeled_box_at_least_1.test.cpp
• tests/twelvefold_way/unlabeled_ball_labeled_box_at_most_1.test.cpp
• tests/twelvefold_way/unlabeled_ball_labeled_box_unrestricted.test.cpp
• tests/twelvefold_way/unlabeled_ball_unlabeled_box_at_least_1.test.cpp
• tests/twelvefold_way/unlabeled_ball_unlabeled_box_at_most_1.test.cpp
• tests/twelvefold_way/unlabeled_ball_unlabeled_box_unrestricted.test.cpp
• tests/util.test.cpp
• tests/xor_convolution.test.cpp

Code

#ifndef TOOLS_MODINT_COMPATIBLE_HPP
#define TOOLS_MODINT_COMPATIBLE_HPP

#include <concepts>
#include <type_traits>

namespace tools {
  template <typename T>
  concept modint_compatible = std::regular<std::remove_cv_t<T>>
    && std::equality_comparable<std::remove_cv_t<T>>
    && std::constructible_from<std::remove_cv_t<T>, bool>
    && std::constructible_from<std::remove_cv_t<T>, char>
    && std::constructible_from<std::remove_cv_t<T>, int>
    && std::constructible_from<std::remove_cv_t<T>, long long>
    && std::constructible_from<std::remove_cv_t<T>, unsigned int>
    && std::constructible_from<std::remove_cv_t<T>, unsigned long long>
    && requires(std::remove_cv_t<T> a, std::remove_cv_t<T> b, int v_int, long long v_ll) {
      { std::remove_cv_t<T>::mod() } -> std::convertible_to<int>;
      { std::remove_cv_t<T>::raw(v_int) } -> std::same_as<std::remove_cv_t<T>>;
      { a.val() } -> std::convertible_to<int>;
      { ++a } -> std::same_as<std::remove_cv_t<T>&>;
      { --a } -> std::same_as<std::remove_cv_t<T>&>;
      { a++ } -> std::same_as<std::remove_cv_t<T>>;
      { a-- } -> std::same_as<std::remove_cv_t<T>>;
      { a += b } -> std::same_as<std::remove_cv_t<T>&>;
      { a -= b } -> std::same_as<std::remove_cv_t<T>&>;
      { a *= b } -> std::same_as<std::remove_cv_t<T>&>;
      { a /= b } -> std::same_as<std::remove_cv_t<T>&>;
      { +a } -> std::same_as<std::remove_cv_t<T>>;
      { -a } -> std::same_as<std::remove_cv_t<T>>;
      { a.pow(v_ll) } -> std::same_as<std::remove_cv_t<T>>;
      { a.inv() } -> std::same_as<std::remove_cv_t<T>>;
      { a + b } -> std::same_as<std::remove_cv_t<T>>;
      { a - b } -> std::same_as<std::remove_cv_t<T>>;
      { a * b } -> std::same_as<std::remove_cv_t<T>>;
      { a / b } -> std::same_as<std::remove_cv_t<T>>;
    };
}

#endif

#line 1 "tools/modint_compatible.hpp"



#include <concepts>
#include <type_traits>

namespace tools {
  template <typename T>
  concept modint_compatible = std::regular<std::remove_cv_t<T>>
    && std::equality_comparable<std::remove_cv_t<T>>
    && std::constructible_from<std::remove_cv_t<T>, bool>
    && std::constructible_from<std::remove_cv_t<T>, char>
    && std::constructible_from<std::remove_cv_t<T>, int>
    && std::constructible_from<std::remove_cv_t<T>, long long>
    && std::constructible_from<std::remove_cv_t<T>, unsigned int>
    && std::constructible_from<std::remove_cv_t<T>, unsigned long long>
    && requires(std::remove_cv_t<T> a, std::remove_cv_t<T> b, int v_int, long long v_ll) {
      { std::remove_cv_t<T>::mod() } -> std::convertible_to<int>;
      { std::remove_cv_t<T>::raw(v_int) } -> std::same_as<std::remove_cv_t<T>>;
      { a.val() } -> std::convertible_to<int>;
      { ++a } -> std::same_as<std::remove_cv_t<T>&>;
      { --a } -> std::same_as<std::remove_cv_t<T>&>;
      { a++ } -> std::same_as<std::remove_cv_t<T>>;
      { a-- } -> std::same_as<std::remove_cv_t<T>>;
      { a += b } -> std::same_as<std::remove_cv_t<T>&>;
      { a -= b } -> std::same_as<std::remove_cv_t<T>&>;
      { a *= b } -> std::same_as<std::remove_cv_t<T>&>;
      { a /= b } -> std::same_as<std::remove_cv_t<T>&>;
      { +a } -> std::same_as<std::remove_cv_t<T>>;
      { -a } -> std::same_as<std::remove_cv_t<T>>;
      { a.pow(v_ll) } -> std::same_as<std::remove_cv_t<T>>;
      { a.inv() } -> std::same_as<std::remove_cv_t<T>>;
      { a + b } -> std::same_as<std::remove_cv_t<T>>;
      { a - b } -> std::same_as<std::remove_cv_t<T>>;
      { a * b } -> std::same_as<std::remove_cv_t<T>>;
      { a / b } -> std::same_as<std::remove_cv_t<T>>;
    };
}

Back to top page