math_mod/garner.hpp

• View this file on GitHub
• Last update: 2025-06-06 19:36:33+09:00
• Include: #include "math_mod/garner.hpp"

Depends on

• math_mod/inv.hpp

Required by

• convolution/convolution_arb.hpp
• convolution/convolution_int.hpp
• fps/fps_arb.hpp

Verified with

• verify/yosupo_convolution/convolution_arbitrary.test.cpp
• verify/yosupo_fps/fps_exp_arb.test.cpp
• verify/yosupo_fps/fps_inv_arb.test.cpp
• verify/yosupo_fps/fps_log_arb.test.cpp

Code

#ifndef KK2_MATH_MOD_GARNER_HPP
#define KK2_MATH_MOD_GARNER_HPP 1

#include <cassert>
#include <vector>

#include "inv.hpp"

namespace kk2 {

template <class T> T garner(const std::vector<T> &d, const std::vector<T> &p) {
    assert(d.size() + 1 == p.size());
    int nm = d.size();
    std::vector<T> kp(nm + 1, 0), rmult(nm + 1, 1);
    for (int ii = 0; ii < nm; ii++) {
        long long x = (d[ii] - kp[ii]) * mod_inversion(rmult[ii], p[ii]) % p[ii];
        if (x < 0) x += p[ii];
        for (int iii = ii + 1; iii < nm + 1; iii++) {
            kp[iii] = (kp[iii] + rmult[iii] * x) % p[iii];
            rmult[iii] = (rmult[iii] * p[ii]) % p[iii];
        }
    }
    return kp[nm];
}

} // namespace kk2

#endif // KK2_MATH_MOD_GARNER_HPP

#line 1 "math_mod/garner.hpp"



#include <cassert>
#include <vector>

#line 1 "math_mod/inv.hpp"



#include <algorithm>

namespace kk2 {

// require: modulo >= 1
template <class T> constexpr T mod_inversion(T a, T modulo) {
    a %= modulo;
    if (a < 0) a += modulo;
    T s = modulo, t = a;
    T m0 = 0, m1 = 1;
    while (t) {
        T u = s / t;
        std::swap(s -= t * u, t);
        std::swap(m0 -= m1 * u, m1);
    }
    if (m0 < 0) m0 += modulo;
    return m0;
}

} // namespace kk2


#line 8 "math_mod/garner.hpp"

namespace kk2 {

template <class T> T garner(const std::vector<T> &d, const std::vector<T> &p) {
    assert(d.size() + 1 == p.size());
    int nm = d.size();
    std::vector<T> kp(nm + 1, 0), rmult(nm + 1, 1);
    for (int ii = 0; ii < nm; ii++) {
        long long x = (d[ii] - kp[ii]) * mod_inversion(rmult[ii], p[ii]) % p[ii];
        if (x < 0) x += p[ii];
        for (int iii = ii + 1; iii < nm + 1; iii++) {
            kp[iii] = (kp[iii] + rmult[iii] * x) % p[iii];
            rmult[iii] = (rmult[iii] * p[ii]) % p[iii];
        }
    }
    return kp[nm];
}

} // namespace kk2

Back to top page