cp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub rniya/cp-library

:heavy_check_mark: Bostan-Mori Algorithm
(src/polynomial/BostanMori.hpp)

BontanMori(Q, P, N)

入力

$d$ 次多項式 $Q$ 及び高々 $d - 1$ 次の多項式 $P$，整数 $N$．

出力

\[\lbrack x^N \rbrack \frac{P(x)}{Q(x)}.\]

計算量

時間計算量 $\mathrm{O}(d \log d \log N)$

LinearRecurrence(a, c, N)

入力

線型漸化式

\[a _ i = \sum _ {j = 1} ^ d c _ j a _{i - j}\]

を満たす数列 $a$ の初めの $d$ 項 $a _ 0, \dots , a _ {d - 1}$ 及び係数列 $c _ 1, \dots , c _ d$，整数 $N$．

出力

数列 $a$ の第 $N$ 項 $a _ N$ の値．

計算量

時間計算量 $\mathrm{O}(d \log d \log N)$

概要

アルゴリズムの詳細については Links にあるページがわかりやすい． ここでは LinearRecurrence(a, c, N) から BostanMori(Q, P, N) への帰着について説明する．

$d + 1$ 項間漸化式

\[a _ i = \sum _ {j = 1} ^ d c _ j a _ {i - j}\]

について，その数列の母関数を

\[G(x) = \sum _ {i = 0} ^ \infty a _ i x ^ i\]

とし，また

\[Q(x) = 1 - \sum _ {i = 1}^d c _ i x ^ i\]

と定めるとき，$G(x) Q(x)$ は漸化式の定義より高々 $d - 1$ 次の多項式 $P(x)$ に一致する． 以上より，

\[a _ N = \lbrack x ^ N \rbrack \frac{P(x)}{Q(x)}\]

となり，これは $\mathrm{O}(d \log d \log N)$ で計算することが可能である．

出題例

Verified with

Code

#pragma once
#include "../atcoder/convolution"

template <typename T> T BostanMori(std::vector<T> Q, std::vector<T> P, long long N) {
    assert(Q[0] == 1);
    assert(P.size() < Q.size());
    const int d = Q.size();
    for (; N; N >>= 1) {
        auto Q_neg = Q;
        for (int i = 1; i < int(Q.size()); i += 2) Q_neg[i] *= -1;
        P = atcoder::convolution(P, Q_neg);
        Q = atcoder::convolution(Q, Q_neg);
        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(d - 1);
        Q.resize(d);
    }
    return P[0];
}

/**
 * @brief compute Nth term of linearly recurrent sequence a_n = \sum_{i = 1}^d c_i a_{n - i}
 *
 * @tparam T F_p
 * @param a first d elements of the sequence a_0, a_1, ... , a_{d - 1}
 * @param c coefficients of the linear recurrence c_1, c_2, ... , c_d
 * @param N the number of term you want to calculate
 * @return T Nth term of linearly recurrent sequence
 */
template <typename T> T LinearRecurrence(std::vector<T> a, std::vector<T> c, long long N) {
    assert(a.size() >= c.size());
    const int d = c.size();
    std::vector<T> Q(d + 1);
    Q[0] = 1;
    for (int i = 0; i < d; i++) Q[i + 1] = -c[i];
    std::vector<T> P = atcoder::convolution(a, Q);
    P.resize(d);
    return BostanMori(Q, P, N);
}
Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
    ~~~~~~~~~~~~~~^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
    ~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: atcoder/convolution.hpp: line -1: no such header
Back to top page