convolution/generalized_convolution.hpp

• View this file on GitHub
• Last update: 2024-12-23 14:40:18+09:00
• Include: #include "convolution/generalized_convolution.hpp"

Required by

• convolution/bitwise_convolution.hpp
• convolution/mul_div_convolution.hpp

Verified with

• test/lc_gcd_convolution.cpp
• test/lc_lcm_convolution.cpp

Code

#pragma once

template <typename T, auto transform, auto inv_transform>
vector<T> generalized_convolution(vector<T> a, vector<T> b) {
    const int n = a.size();
    transform(a);
    transform(b);
    for (int i = 0; i < n; ++i) {
        a[i] *= b[i];
    }
    inv_transform(a);
    return a;
}

#line 2 "convolution/generalized_convolution.hpp"

template <typename T, auto transform, auto inv_transform>
vector<T> generalized_convolution(vector<T> a, vector<T> b) {
    const int n = a.size();
    transform(a);
    transform(b);
    for (int i = 0; i < n; ++i) {
        a[i] *= b[i];
    }
    inv_transform(a);
    return a;
}

Back to top page