cp-library

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

View the Project on GitHub rniya/cp-library

:heavy_check_mark: Multipoint Evaluation
(src/polynomial/multipoint_evaluation.hpp)

入力

$N - 1$ 次多項式 $f(x)$ 及び数列 $x _ 0, \dots , x _ {M - 1}$．

出力

評価値 $f(x _ 0), \dots , f(x _ {M - 1})$．

計算量

時間計算量 $\mathrm{O}(M \log ^ 2 M + N \log N)$

概要

剰余の定理より $f(a) = f(x) \bmod (x - a)$ であるから $f(x _ 0) \bmod (x - x _ 0), f(x _ 1) \bmod (x - x _ 1), \dots , f(x _ {M - 1}) \bmod (x - x _ {M - 1})$ が求まれば良い．

ここで，次のような各ノードに多項式をもつ根付き 2 分木 (subproduct tree) を構築する． まず，木は $M$ 個の葉ノードをもち，各ノードには $x - x _ 0, x - x _ 1, \dots , x - x _ {M - 1}$ が書かれている． そして，葉以外のノードにはその 2 つの子ノードに書かれた多項式の積が書かれている． subproduct tree は $\mathrm{O}(M \log ^2 M)$ 時間で構築可能である．

次に根の多項式を $f \bmod (x - x _ 0) (x - x _ 1) \dots (x - x _ {M - 1})$ に書き換える． これは $\mathrm{O}((N + M) \log (N + M))$ 時間かかる． また，多項式 $f, g, h$ に対して $(f \bmod g h) \bmod g = f \bmod g$ が成り立つことから，根から葉に逆方向に向かって $f$ をそのノードに書かれた多項式で割った余りを計算できる． これは最初の構築と同様で $\mathrm{O}(M \log ^ 2 M)$ 時間で処理できる．

こうして最終的に葉ノードに書かれた値が求めたかった評価値である．

TODO:

middle product を利用した高速化

出題例

Depends on

Verified with

Code

#pragma once
#include <vector>
#include "FormalPowerSeries.hpp"

template <typename T> struct subproduct_tree {
    using poly = FormalPowerSeries<T>;
    int m;
    std::vector<poly> prod;
    subproduct_tree(const std::vector<T>& x) : m(x.size()) {
        int k = 1;
        while (k < m) k <<= 1;
        prod.assign(k << 1, {1});
        for (int i = 0; i < m; i++) prod[k + i] = {-x[i], 1};
        for (int i = k - 1; i > 0; i--) prod[i] = prod[i << 1] * prod[i << 1 | 1];
    }

    int size() const { return prod.size() >> 1; }

    poly mid_prod(const poly& a, const poly& b) const {}

    std::vector<T> multipoint_evaluation(poly f) const {
        std::vector<poly> rem(size() << 1);
        rem[1] = f % prod[1];
        for (int i = 2; i < size() + m; i++) rem[i] = rem[i >> 1] % prod[i];
        std::vector<T> res(m);
        for (int i = 0; i < m; i++) res[i] = (rem[size() + i].empty() ? 0 : rem[size() + i][0]);
        return res;
    }
};
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 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