modint/base.hpp

• View this file on GitHub
• Last update: 2023-10-26 11:41:06+09:00
• Include: #include "modint/base.hpp"

Required by

• Arbitrary Convolution (convolution/arbitrary_ntt.hpp)
• Convolution $\pmod{2^{64}}$ (convolution/convolution_mod_2_64.hpp)
• NTT Convolution (convolution/ntt.hpp)
• $f(g(x))$ (fps/composition_of_fps.hpp)
• $f(x)$ の逆関数 (fps/compositional_inverse_of_fps.hpp)
• Formal Power Series (fps/fps.hpp)
• Formal Power Series (Sparse) (fps/fps_sparse.hpp)
• $\sqrt{f}$ (fps/fps_sqrt.hpp)
• $[x^i]c = \sum_{j} [x^{i+j}]a [x^j]b$ (fps/middle_product.hpp)
• Multipoint Evaluation (fps/multipoint_evaluation.hpp)
• Polynomial Interpolation (fps/polynomial_interpolation.hpp)
• $\prod_{i=0}^n f_i$ (fps/product_of_fps.hpp)
• $\prod (1 - x^{a_i}) \mod x^d$ (fps/product_of_one_minus_xn.hpp)
• $\prod (1 + x^{a_i}) \mod x^d$ (fps/product_of_one_plus_xn.hpp)
• $\sum_i (\sum_n A_n^i) x^i$ (fps/sums_of_powers.hpp)
• $f(x + c)$ (fps/taylor_shift.hpp)
• Bernoulli Number (math/bernoulli_number.hpp)
• Binomial Coefficient (math/binomial.hpp)
• Catalan's Convolution Formula (math/catalan_convolution.hpp)
• Catalan Number (math/catalan_number.hpp)
• math/factorial_mod_998.hpp
• Mod Inv (math/mod_inv.hpp)
• Mod Sqrt (math/mod_sqrt.hpp)
• Partition Function (math/partition_function.hpp)
• Stirling Numbers of the First Kind (math/stirling_number_1st.hpp)
• Stirling Numbers of the Second Kind (math/stirling_number_2nd.hpp)
• matrix/det_arbitrary_mod.hpp
• modint/dynamic_modint.hpp
• modint/modint.hpp
• modint/modint61.hpp
• modint/montgomery_modint.hpp
• Rolling Hash (string/rolling_hash.hpp)
• Rooted Tree Hash (tree/rooted_tree_hash.hpp)
• Hash structure (utility/hash.hpp)

Verified with

• test/aoj/aoj_2444.test.cpp
• test/aoj/aoj_2863.test.cpp
• test/aoj/aoj_3361.test.cpp
• test/convolution/Bitwise_And_Convolution.test.cpp
• test/convolution/Bitwise_OR_Convolution.test.cpp
• test/convolution/Bitwise_Xor_Convolution.test.cpp
• test/convolution/Convolution.test.cpp
• test/convolution/Convolution_Mod_1000000007.test.cpp
• test/convolution/Convolution_Mod_2_64.test.cpp
• test/convolution/Gcd_Convolution.test.cpp
• test/convolution/Lcm_Convolution.test.cpp
• test/convolution/Subset_Convolution.test.cpp
• test/data_structure/Deque_Operate_All_Composite.test.cpp
• test/data_structure/Dynamic_Sequence_Range_Affine_Range_Sum.test.cpp
• test/data_structure/Point_Set_Range_Composite.test.cpp
• test/data_structure/Queue_Operate_All_Composite.test.cpp
• test/data_structure/Range_Affine_Point_Get.test.cpp
• test/data_structure/Range_Affine_Point_Get_Dynamic_Segtree.test.cpp
• test/data_structure/Range_Affine_Range_Sum.test.cpp
• test/data_structure/Vertex_Set_Path_Compositie.test.cpp
• test/math/Berunoulli_Number.test.cpp
• test/math/Binomial_Coefficient_Prime_Mod.test.cpp
• test/math/Catalan_Convolution.test.cpp
• test/math/Factorial.test.cpp
• test/math/Kth_term_of_Linearly_Recurrent_Sequence.test.cpp
• test/math/Partition_Function_FPS.test.cpp
• test/math/Partition_Function_Pentagonal.test.cpp
• test/math/Pow.test.cpp
• test/math/Sqrt_Mod.test.cpp
• test/math/Stirling_Number_of_the_First_Kind.test.cpp
• test/math/Stirling_Number_of_the_Second_Kind.test.cpp
• test/math/Sum_of_Totient_Function.test.cpp
• test/math/sharp_p_subset_sum.test.cpp
• test/matrix/Determinant_of_Matrix.test.cpp
• test/matrix/Determinant_of_Matrix_2.test.cpp
• test/matrix/Determinant_of_Matrix_Arbitrary_Mod.test.cpp
• test/matrix/Inverse_Matrix.test.cpp
• test/matrix/Matrix_Product.test.cpp
• test/matrix/Pow_of_Matrix.test.cpp
• test/matrix/Rank_of_Matrix.test.cpp
• test/matrix/System_of_Linear_Equations.test.cpp
• test/polynomial/Composition_of_Formal_Power_Series.test.cpp
• test/polynomial/Compositional_Inverse_of_Formal_Power_Series.test.cpp
• test/polynomial/Division_of_Polynomials.test.cpp
• test/polynomial/Exp_of_Formal_Power_Series.test.cpp
• test/polynomial/Exp_of_Formal_Power_Series_Sparse.test.cpp
• test/polynomial/Inv_of_Formal_Power_Series.test.cpp
• test/polynomial/Inv_of_Formal_Power_Series_Sparse.test.cpp
• test/polynomial/Log_of_Formal_Power_Series.test.cpp
• test/polynomial/Log_of_Formal_Power_Series_Sparse.test.cpp
• test/polynomial/Multipoint_Evaluation.test.cpp
• test/polynomial/Polynomial_Interpolation.test.cpp
• test/polynomial/Polynomial_Taylor_Shift.test.cpp
• test/polynomial/Pow_of_Formal_Power_Series.test.cpp
• test/polynomial/Pow_of_Formal_Power_Series_Sparse.test.cpp
• test/polynomial/Product_of_Polynomial_Sequence.test.cpp
• test/polynomial/Sqrt_of_Formal_Power_Series.test.cpp
• test/polynomial/Sqrt_of_Formal_Power_Series_Sparse.test.cpp
• test/set_function/Exp_of_Set_Power_Series.test.cpp
• test/set_function/Polynomial_Composite_Set_Power_Series.test.cpp
• test/tree/Frequency_Table_of_Tree_Distance_MODE_0.test.cpp
• test/tree/Frequency_Table_of_Tree_Distance_MODE_1.test.cpp
• test/tree/Frequency_Table_of_Tree_Distance_MODE_2.test.cpp
• test/tree/Point_Set_Tree_Path_Composition_Sum_Fixed_Root.test.cpp
• test/tree/Rooted_Tree_Isomorphism_Classification.test.cpp
• test/tree/Tree_Path_Composite_Sum.test.cpp
• test/yuki/yuki_1145.test.cpp
• test/yuki/yuki_1302.test.cpp
• test/yuki/yuki_1796.test.cpp
• test/yuki/yuki_2747.test.cpp

Code

#pragma once

#include <concepts>
#include <iostream>
#include <utility>

namespace ebi {

template <class T>
concept Modint = requires(T a, T b) {
    a + b;
    a - b;
    a * b;
    a / b;
    a.inv();
    a.val();
    a.pow(std::declval<long long>());
    T::mod();
};

template <Modint mint> std::istream &operator>>(std::istream &os, mint &a) {
    long long x;
    os >> x;
    a = x;
    return os;
}

template <Modint mint>
std::ostream &operator<<(std::ostream &os, const mint &a) {
    return os << a.val();
}

}  // namespace ebi

#line 2 "modint/base.hpp"

#include <concepts>
#include <iostream>
#include <utility>

namespace ebi {

template <class T>
concept Modint = requires(T a, T b) {
    a + b;
    a - b;
    a * b;
    a / b;
    a.inv();
    a.val();
    a.pow(std::declval<long long>());
    T::mod();
};

template <Modint mint> std::istream &operator>>(std::istream &os, mint &a) {
    long long x;
    os >> x;
    a = x;
    return os;
}

template <Modint mint>
std::ostream &operator<<(std::ostream &os, const mint &a) {
    return os << a.val();
}

}  // namespace ebi

Back to top page