cp-algo/math/common.hpp

• View this file on GitHub
• Last update: 2024-06-29 00:06:31+02:00
• Include: #include "cp-algo/math/common.hpp"

Required by

• cp-algo/linalg/frobenius.hpp
• cp-algo/linalg/matrix.hpp
• cp-algo/linalg/vector.hpp
• cp-algo/math/combinatorics.hpp
• cp-algo/math/fft.hpp
• cp-algo/math/modint.hpp
• cp-algo/math/number_theory.hpp
• cp-algo/math/poly.hpp
• cp-algo/math/poly/impl/div.hpp
• cp-algo/math/poly/impl/euclid.hpp

Verified with

• Binomial Coefficient (Prime Mod) (verify/combi/binom.test.cpp)
• Range Affine Range Sum (verify/data_structures/segtree/range_affine_range_sum.test.cpp)
• Dynamic Range Affine Range Sum (verify/data_structures/treap/dynamic_sequence_range_affine_range_sum.test.cpp)
• Characteristic Polynomial (verify/linalg/characteristic.test.cpp)
• Matrix Determinant (verify/linalg/det.test.cpp)
• Inverse Matrix (verify/linalg/inv.test.cpp)
• Pow of Matrix (verify/linalg/pow.test.cpp)
• Pow of Matrix (Frobenius) (verify/linalg/pow_fast.test.cpp)
• Matrix Product (verify/linalg/prod.test.cpp)
• Matrix Product (dynamic modint) (verify/linalg/prod_dynamic_modint.test.cpp)
• Rank of Matrix (verify/linalg/rank.test.cpp)
• System of Linear Equations (verify/linalg/system.test.cpp)
• Discrete Logarithm (verify/number_theory/discrete_log.test.cpp)
• Factorize (verify/number_theory/factorize.test.cpp)
• Sqrt Mod (verify/number_theory/modsqrt.test.cpp)
• Primality Test (verify/number_theory/primality.test.cpp)
• Primitive Root (verify/number_theory/primitive_root.test.cpp)
• Convolution mod $10^9+7$ (verify/poly/convolution107.test.cpp)
• Division of Polynomials (verify/poly/div.test.cpp)
• Find Linear Recurrence (verify/poly/find_linrec.test.cpp)
• Polynomial Interpolation (verify/poly/inter.test.cpp)
• Inv of Power Series (verify/poly/inv.test.cpp)
• Inv of Polynomials (verify/poly/inv_mod.test.cpp)
• Consecutive Terms of Linear Recursion (verify/poly/linrec_consecutive.test.cpp)
• Pow of Power Series (verify/poly/pow.test.cpp)
• Polynomial Root Finding (verify/poly/roots.test.cpp)
• Sqrt of Power Series (verify/poly/sqrt.test.cpp)
• Polynomial Taylor Shift (verify/poly/taylor.test.cpp)
• Wildcard Pattern Matching (verify/poly/wildcard.test.cpp)

Code

#ifndef CP_ALGO_MATH_COMMON_HPP
#define CP_ALGO_MATH_COMMON_HPP
#include <functional>
#include <cstdint>
namespace cp_algo::math {
#ifdef CP_ALGO_MAXN
    const int maxn = CP_ALGO_MAXN;
#else
    const int maxn = 1 << 19;
#endif
    const int magic = 64; // threshold for sizes to run the naive algo

    auto bpow(auto const& x, int64_t n, auto const& one, auto op) {
        if(n == 0) {
            return one;
        } else {
            auto t = bpow(x, n / 2, one, op);
            t = op(t, t);
            if(n % 2) {
                t = op(t, x);
            }
            return t;
        }
    }
    auto bpow(auto x, int64_t n, auto ans) {
        return bpow(x, n, ans, std::multiplies{});
    }
    template<typename T>
    T bpow(T const& x, int64_t n) {
        return bpow(x, n, T(1));
    }
}
#endif // CP_ALGO_MATH_COMMON_HPP

#line 1 "cp-algo/math/common.hpp"


#include <functional>
#include <cstdint>
namespace cp_algo::math {
#ifdef CP_ALGO_MAXN
    const int maxn = CP_ALGO_MAXN;
#else
    const int maxn = 1 << 19;
#endif
    const int magic = 64; // threshold for sizes to run the naive algo

    auto bpow(auto const& x, int64_t n, auto const& one, auto op) {
        if(n == 0) {
            return one;
        } else {
            auto t = bpow(x, n / 2, one, op);
            t = op(t, t);
            if(n % 2) {
                t = op(t, x);
            }
            return t;
        }
    }
    auto bpow(auto x, int64_t n, auto ans) {
        return bpow(x, n, ans, std::multiplies{});
    }
    template<typename T>
    T bpow(T const& x, int64_t n) {
        return bpow(x, n, T(1));
    }
}

Back to top page