Relaxed Convolution
(src/convolution/RelaxedConvolution.hpp)

• View this file on GitHub
• Last update: 2024-06-01 02:28:17+09:00
• Include: #include "src/convolution/RelaxedConvolution.hpp"

概要

未知の $N$ 次多項式 $f, g$ があり，$h(x) = f(x) g(x)$ であるとき，$i = 0, 1, \dots , N$ の順に以下のクエリを計 $\mathrm{O}(N \log ^ 2 N)$ 時間で処理する．

• $[x ^ i] f(x), [x ^ i] g(x)$ が与えられるので，$[x ^ i] h(x)$ を返す．

出題例

• AtCoder Beginner Contest 230 H - Bullion
• AtCoder Beginner Contest 315 Ex - Typical Convolution Problem

Links

• オンライン畳み込み - Qiita

Verified with

• test/yosupo/convolution_mod.relaxedconvolution.test.cpp

Code

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

template <class T> class RelaxedConvolution {
    int n;
    std::vector<T> f, g, h;

  public:
    RelaxedConvolution() : n(0) {}

    T query(T a, T b) {
        f.emplace_back(a);
        g.emplace_back(b);
        h.emplace_back(0);
        if (n > 0) h.emplace_back(0);
        int p = __builtin_ctz(n + 2);
        for (int k = 0; k <= p; k++) {
            {
                std::vector<T> f1(f.begin() + (1 << k) - 1, f.begin() + (1 << (k + 1)) - 1);
                std::vector<T> g1(g.end() - (1 << k), g.end());
                auto c1 = atcoder::convolution(f1, g1);
                for (int i = 0; i < (1 << (k + 1)) - 1; i++) h[n + i] += c1[i];
            }
            if ((1 << p) == n + 2 and k == p - 1) break;
            {
                std::vector<T> f2(f.end() - (1 << k), f.end());
                std::vector<T> g2(g.begin() + (1 << k) - 1, g.begin() + (1 << (k + 1)) - 1);
                auto c2 = atcoder::convolution(f2, g2);
                for (int i = 0; i < (1 << (k + 1)) - 1; i++) h[n + i] += c2[i];
            }
        }
        return h[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