Convolution (Arbitary mod)
(src/convolution/convolution_arbitary_mod.hpp)

• View this file on GitHub
• Last update: 2024-06-01 01:35:37+09:00
• Include: #include "src/convolution/convolution_arbitary_mod.hpp"

Verified with

• test/yosupo/convolution_mod_1000000007.test.cpp

Code

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

template <class mint>
std::vector<mint> convolution_arbitary_mod(const std::vector<mint>& a, const std::vector<mint>& b) {
    int n = a.size(), m = b.size();
    if (n == 0 or m == 0) return {};
    static constexpr unsigned long long MOD1 = 754974721;  // 2^24
    static constexpr unsigned long long MOD2 = 167772161;  // 2^25
    static constexpr unsigned long long MOD3 = 469762049;  // 2^26
    using mint1 = atcoder::static_modint<MOD1>;
    using mint2 = atcoder::static_modint<MOD2>;
    using mint3 = atcoder::static_modint<MOD3>;

    const mint2 i1 = mint2(MOD1).inv();
    const mint3 i2 = mint3(MOD2).inv();
    const mint3 i1i2 = mint3(MOD1).inv() * i2;
    const mint m1 = MOD1, m1m2 = m1 * MOD2;

    std::vector<mint1> a1(n), b1(m);
    std::vector<mint2> a2(n), b2(m);
    std::vector<mint3> a3(n), b3(m);
    for (int i = 0; i < n; i++) {
        a1[i] = a[i].val();
        a2[i] = a[i].val();
        a3[i] = a[i].val();
    }
    for (int i = 0; i < m; i++) {
        b1[i] = b[i].val();
        b2[i] = b[i].val();
        b3[i] = b[i].val();
    }
    auto c1 = convolution(a1, b1);
    auto c2 = convolution(a2, b2);
    auto c3 = convolution(a3, b3);

    std::vector<mint> c(n + m - 1);
    for (int i = 0; i < n + m - 1; i++) {
        int v1 = c1[i].val();
        int v2 = (i1 * (c2[i] - v1)).val();
        int v3 = (i1i2 * (c3[i] - v1) - i2 * v2).val();
        c[i] = v1 + m1 * v2 + m1m2 * v3;
    }

    return c;
}

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