Difference Product (Vandermonde's Determinant)
(src/polynomial/difference_product.hpp)

• View this file on GitHub
• Last update: 2024-05-22 00:21:24+09:00
• Include: #include "src/polynomial/difference_product.hpp"

入力

長さ $N$ の数列 $x _ 0, \dots , x _ {N - 1}$．

出力

差積の値． すなわち，

\[\prod _ {0 \le i \lt j \le n} (x _ j - x _ i).\]

計算量

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

出題例

• yukicoder No.2513 Power Eraser

Links

• 差積の $2$ 乗？

Depends on

• Formal Power Series (src/polynomial/FormalPowerSeries.hpp)

Verified with

• test/yukicoder/2513.test.cpp

Code

#pragma once
#include "FormalPowerSeries.hpp"

template <typename T> T difference_product(const std::vector<int>& x) {
    int n = x.size(), k = 1;
    while (k < n) k <<= 1;
    std::vector<FormalPowerSeries<T>> prod(k << 1, {1});
    for (int i = 0; i < n; i++) prod[k + i] = {-x[i], 1};
    for (int i = k - 1; i > 0; i--) prod[i] = prod[i << 1] * prod[i << 1 | 1];
    std::vector<FormalPowerSeries<T>> rem(k << 1);
    rem[0] = {1};
    for (int i = 1; i < k + n; i++) {
        rem[i] = rem[i >> 1];
        if (~i & 1) rem[i] *= prod[i | 1];
        rem[i] %= prod[i];
    }
    T res = 1;
    for (int i = 0; i < n; i++) res *= (rem[k + i].empty() ? 0 : rem[k + 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