Convolution
(library/convolution/convolution.hpp)

• View this file on GitHub
• Last update: 2022-01-31 13:34:34+09:00
• Include: #include "library/convolution/convolution.hpp"

transform_convolution

• シグネチャ

  template <typename T, auto transform, auto inv_transform, auto mul = default_operator::mul<T>>
  std::vector<T> transform_convolution(std::vector<T> a, std::vector<T> b) // (1)
  template <typename T, auto transform, auto inv_transform, auto mul = default_operator::mul<T>>
  std::vector<T> transform_convolution(std::vector<std::vector<T>> a) // (2)
  

• 概要

  長さ $N$ の列 $(A_0,A_1,\ldots,A_{N-1})$ および $(B_0,B_1,\ldots,B_{N-1})$ を畳み込みます．即ち，長さ $N$ の列 $(C_0,C_1,\ldots,C_{N-1})$ であって，各 $k=0,\ldots,N-1$ に対して以下を満たす列を計算します．

  \[C _ k = \sum _ { i \oplus j = k } A _ i \cdot B _ j\]

  ここで，$\oplus$ は $\mathbb{Z}$ 上の二項演算です．

  この関数は $\odot$ を列の各点積を取る演算として，$\mathcal{F}[A]\odot \mathcal{F}[B]=\mathcal{F}[C]$ を満たす変換行列 $\mathcal{F}$ とその逆行列 $\mathcal{F}^{-1}$ が存在することが必要であり，この条件の下で $C=\mathcal{F}^{-1}\left[\mathcal{F}[A]\odot \mathcal{F}[B]\right]$ として畳み込みを計算します．

  以下，この畳み込みを $C=A\ast B$ と表記します．

• テンプレート引数

  • T: 列の要素の型．
  • transform: 列に対して inplace に線形変換 $\mathcal{F}$ を作用させる関数
  • transform_inv: 列に対して inplace に線形変換 $\mathcal{F}^{-1}$ を作用させる関数
  • mul: 各点積 $\odot$ を計算するための T 上の乗算．デフォルトでは operator* が呼ばれるようになっています．

• 返り値

  1. $A\ast B$
  2. $\mathcal{A}^0\ast \mathcal{A}^1\ast \cdots$ (ここで，$\mathcal{A}^i$ は列 $(A_0^i,\ldots,A_{N-1}^i)$ を表す)

• 時間計算量

  transform の計算量を $\Theta(f(N))$, transform_inv の計算量を $\Theta(g(N))$ として

  1. $\Theta(f(N)+g(N))$
  2. 列の数を $K$ として，$\Theta(K\cdot(f(N)+g(N)))$

Depends on

• Default Operator (library/util/default_operator.hpp)

Required by

• Bitwise And Convolution (library/convolution/and_convolution.hpp)
• GCD Convolution (library/convolution/gcd_convolution.hpp)
• LCM Convolution (library/convolution/lcm_convolution.hpp)
• Bitwise Or Convolution (library/convolution/or_convolution.hpp)
• Bitwise Xor Convolution (library/convolution/xor_convolution.hpp)

Verified with

• test/src/convolution/and_convolution/and_convolution.test.cpp
• test/src/convolution/gcd_convolution/gcd_convolution.test.cpp
• test/src/convolution/gcd_convolution/lcms.test.cpp
• test/src/convolution/lcm_convolution/lcm_convolution.test.cpp
• test/src/convolution/xor_convolution/xor_convolution.test.cpp

Code

#ifndef SUISEN_CONVOLUTION
#define SUISEN_CONVOLUTION

#include <cassert>
#include <vector>

#include "library/util/default_operator.hpp"

namespace suisen {
    namespace convolution {
        template <typename T, auto transform, auto inv_transform, auto mul = default_operator::mul<T>>
        std::vector<T> transform_convolution(std::vector<T> a, std::vector<T> b) {
            const std::size_t n = a.size(), m = b.size();
            assert(n == m);
            transform(a), transform(b);
            for (std::size_t i = 0; i < n; ++i) a[i] = mul(a[i], b[i]);
            inv_transform(a);
            return a;
        }
        template <typename T, auto transform, auto inv_transform, auto mul = default_operator::mul<T>>
        std::vector<T> transform_convolution(std::vector<std::vector<T>> a) {
            const std::size_t num = a.size();
            assert(num);
            const std::size_t n = a[0].size();
            for (auto &v : a) {
                assert(n == int(v.size()));
                transform(v);
            }
            auto &res = a[0];
            for (int i = 1; i < num; ++i) {
                for (int j = 0; j < n; ++j) res[j] = mul(res[j], a[i][j]);
            }
            inv_transform(res);
            return res;
        }
    }
} // namespace suisen


#endif // SUISEN_CONVOLUTION

#line 1 "library/convolution/convolution.hpp"



#include <cassert>
#include <vector>

#line 1 "library/util/default_operator.hpp"



namespace suisen {
    namespace default_operator {
        template <typename T>
        auto zero() -> decltype(T { 0 }) { return T { 0 }; }
        template <typename T>
        auto one()  -> decltype(T { 1 }) { return T { 1 }; }
        template <typename T>
        auto add(const T &x, const T &y) -> decltype(x + y) { return x + y; }
        template <typename T>
        auto sub(const T &x, const T &y) -> decltype(x - y) { return x - y; }
        template <typename T>
        auto mul(const T &x, const T &y) -> decltype(x * y) { return x * y; }
        template <typename T>
        auto div(const T &x, const T &y) -> decltype(x / y) { return x / y; }
        template <typename T>
        auto mod(const T &x, const T &y) -> decltype(x % y) { return x % y; }
        template <typename T>
        auto neg(const T &x) -> decltype(-x) { return -x; }
        template <typename T>
        auto inv(const T &x) -> decltype(one<T>() / x)  { return one<T>() / x; }
    } // default_operator
    namespace default_operator_noref {
        template <typename T>
        auto zero() -> decltype(T { 0 }) { return T { 0 }; }
        template <typename T>
        auto one()  -> decltype(T { 1 }) { return T { 1 }; }
        template <typename T>
        auto add(T x, T y) -> decltype(x + y) { return x + y; }
        template <typename T>
        auto sub(T x, T y) -> decltype(x - y) { return x - y; }
        template <typename T>
        auto mul(T x, T y) -> decltype(x * y) { return x * y; }
        template <typename T>
        auto div(T x, T y) -> decltype(x / y) { return x / y; }
        template <typename T>
        auto mod(T x, T y) -> decltype(x % y) { return x % y; }
        template <typename T>
        auto neg(T x) -> decltype(-x) { return -x; }
        template <typename T>
        auto inv(T x) -> decltype(one<T>() / x)  { return one<T>() / x; }
    } // default_operator
} // namespace suisen


#line 8 "library/convolution/convolution.hpp"

namespace suisen {
    namespace convolution {
        template <typename T, auto transform, auto inv_transform, auto mul = default_operator::mul<T>>
        std::vector<T> transform_convolution(std::vector<T> a, std::vector<T> b) {
            const std::size_t n = a.size(), m = b.size();
            assert(n == m);
            transform(a), transform(b);
            for (std::size_t i = 0; i < n; ++i) a[i] = mul(a[i], b[i]);
            inv_transform(a);
            return a;
        }
        template <typename T, auto transform, auto inv_transform, auto mul = default_operator::mul<T>>
        std::vector<T> transform_convolution(std::vector<std::vector<T>> a) {
            const std::size_t num = a.size();
            assert(num);
            const std::size_t n = a[0].size();
            for (auto &v : a) {
                assert(n == int(v.size()));
                transform(v);
            }
            auto &res = a[0];
            for (int i = 1; i < num; ++i) {
                for (int j = 0; j < n; ++j) res[j] = mul(res[j], a[i][j]);
            }
            inv_transform(res);
            return res;
        }
    }
} // namespace suisen

Back to top page