Bostan-Mori法 (lib/math/bostan_mori.hpp)

• View this file on GitHub
• Last update: 2026-02-15 03:51:00+09:00
• Include: #include "lib/math/bostan_mori.hpp"

Depends on

• 畳み込み (lib/fft/ntt.hpp)
• lib/internal/internal_fft.hpp
• Montgomery modular multiplication (lib/internal/internal_math.hpp)
• lib/internal/internal_type_traits.hpp
• lib/math/modint.hpp
• lib/template/template.hpp

Verified with

• test/yosupo/math/bostan_mori.test.cpp

Code

#pragma once
#include <vector>
#include "fft/ntt.hpp"

/**
 * @brief Bostan-Mori法
 *
 * @tparam mint
 * @param p
 * @param q
 * @param n
 * @return mint
 */
template <class mint>
mint bostan_mori(std::vector<mint> p, std::vector<mint> q, std::int64_t n) {
    if (n < 0) return 0;
    while (n > 0) {
        if (p.size() >= q.size()) p.resize(q.size() - 1);
        std::vector<mint> q_minus = q;
        for (int i = 1; i < (int)q_minus.size(); i += 2) q_minus[i] = -q_minus[i];
        p = convolution(p, q_minus);
        q = convolution(q, q_minus);
        for (int i = (n & 1); i < (int)p.size(); i += 2) p[i >> 1] = p[i];
        for (int i = 0; i < (int)q.size(); i += 2) q[i >> 1] = q[i];
        p.resize((p.size() + !(n & 1)) / 2);
        q.resize((q.size() + 1) / 2);
        n >>= 1;
    }
    return p[0] / q[0];
}

/**
 * @brief 線形漸化式のN項目
 * a_i = \sum_{j=1}^d c_j a_{i-j} (i >= d)
 *
 * @tparam mint
 * @param a initial terms a_0, ..., a_{d-1}
 * @param c recurrence coefficients c_1, ..., c_d
 * @param n
 * @return mint
 */
template <class mint>
mint kth_term(std::vector<mint> a, std::vector<mint> c, std::int64_t n) {
    assert(a.size() == c.size());
    int d = a.size();
    if (n < d) return a[n];
    std::vector<mint> q(d + 1);
    q[0] = 1;
    for (int i = 0; i < d; ++i) q[i + 1] = -c[i];
    std::vector<mint> p = convolution(a, q);
    p.resize(d);
    return bostan_mori(p, q, n);
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: fft/ntt.hpp: line -1: no such header

Back to top page