math/internal_math.hpp

• View this file on GitHub
• Last update: 2023-08-31 02:52:44+09:00
• Include: #include "math/internal_math.hpp"

Required by

• Arbitrary Convolution (convolution/arbitrary_convolution.hpp)
• Convolution (convolution/convolution.hpp)
• Convolution 2D (convolution/convolution_2d.hpp)
• Convolution $\pmod{2^{64}}$ (convolution/convolution_mod_2_64.hpp)
• NTT (convolution/ntt.hpp)
• Formal Power Series (Arbitrary mod) (fps/arbitrary_mod_fps.hpp)
• $f(g(x))$ ( $O(N\log^2{N})$ ) (fps/composition_of_fps.hpp)
• $f(x)$ の逆関数 ( $O(N^2)$ ) (fps/compositional_inverse_of_fps_old.hpp)
• $[x^i]c = \sum_{j} [x^{i+j}]a [x^j]b$ (fps/middle_product.hpp)
• $f^k \mod g$ (fps/middle_product_arbitrary.hpp)
• Formal Power Series (NTT Friendly) (fps/ntt_friendly_fps.hpp)
• Wildcard Pattern Matching (string/wildcard_pattern_matching.hpp)

Verified with

• test/convolution/Convolution.test.cpp
• test/convolution/Convolution_2D.test.cpp
• test/convolution/Convolution_Mod_1000000007.test.cpp
• test/convolution/Convolution_Mod_2_64.test.cpp
• test/math/Berunoulli_Number.test.cpp
• test/math/Catalan_Convolution.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/Sharp_P_Subset_Sum.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_Powers_Iota.test.cpp
• test/polynomial/Composition_of_Formal_Power_Series.test.cpp
• test/polynomial/Composition_of_Formal_Power_Series_Large.test.cpp
• test/polynomial/Compositional_Inverse_of_Formal_Power_Series.test.cpp
• test/polynomial/Compositional_Inverse_of_Formal_Power_Series_Large.test.cpp
• test/polynomial/Division_of_Polynomials.test.cpp
• test/polynomial/Exp_of_Formal_Power_Series.test.cpp
• test/polynomial/Inv_of_Formal_Power_Series.test.cpp
• test/polynomial/Log_of_Formal_Power_Series.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/Product_of_Polynomial_Sequence.test.cpp
• test/polynomial/Shift_of_Sampling_Points_of_Polynomial.test.cpp
• test/polynomial/Sqrt_of_Formal_Power_Series.test.cpp
• test/polynomial/Sqrt_of_Formal_Power_Series_Sparse.test.cpp
• test/string/Wildcard_Pattern_Matching.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/yuki/yuki_1112.test.cpp
• test/yuki/yuki_1145.test.cpp
• test/yuki/yuki_1302.test.cpp
• test/yuki/yuki_1720.test.cpp
• test/yuki/yuki_1796.test.cpp
• test/yuki/yuki_1857.test.cpp

Code

#pragma once

#include <cassert>

namespace ebi {

namespace internal {

constexpr int primitive_root_constexpr(int m) {
    if (m == 2) return 1;
    if (m == 167772161) return 3;
    if (m == 469762049) return 3;
    if (m == 754974721) return 11;
    if (m == 998244353) return 3;
    if (m == 880803841) return 26;
    if (m == 924844033) return 5;
    return -1;
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);

}  // namespace internal

}  // namespace ebi

#line 2 "math/internal_math.hpp"

#include <cassert>

namespace ebi {

namespace internal {

constexpr int primitive_root_constexpr(int m) {
    if (m == 2) return 1;
    if (m == 167772161) return 3;
    if (m == 469762049) return 3;
    if (m == 754974721) return 11;
    if (m == 998244353) return 3;
    if (m == 880803841) return 26;
    if (m == 924844033) return 5;
    return -1;
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);

}  // namespace internal

}  // namespace ebi

Back to top page