Convolution (Index bitwise AND)
(Mylib/Convolution/convolution_and.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

• convolution_and(f[N], g[N])
  • Nは2の累乗
  • k in [0, N)について、$h_k = \sum_{k=i \cap j} f_i * g_j$を求める。

Requirements

Notes

Problems

References

Depends on

• Fast Möbius transform (Supersets) (Mylib/Convolution/fast_mobius_transform_superset.cpp)
• Fast Zeta transform (Supersets) (Mylib/Convolution/fast_zeta_transform_superset.cpp)

Verified with

• test/yosupo-judge/bitwise_and_convolution/main.test.cpp

Code

#pragma once
#include <vector>
#include "Mylib/Convolution/fast_mobius_transform_superset.cpp"
#include "Mylib/Convolution/fast_zeta_transform_superset.cpp"

namespace haar_lib {
  template <typename T>
  std::vector<T> convolution_and(std::vector<T> f, std::vector<T> g) {
    f = fast_zeta_transform_superset(f);
    g = fast_zeta_transform_superset(g);
    for (size_t i = 0; i < f.size(); ++i) f[i] *= g[i];
    f = fast_mobius_transform_superset(f);
    return f;
  }
}  // namespace haar_lib

#line 2 "Mylib/Convolution/convolution_and.cpp"
#include <vector>
#line 2 "Mylib/Convolution/fast_mobius_transform_superset.cpp"
#include <cassert>
#include <functional>
#line 5 "Mylib/Convolution/fast_mobius_transform_superset.cpp"

namespace haar_lib {
  template <typename T, typename Func = std::minus<T>>
  std::vector<T> fast_mobius_transform_superset(std::vector<T> f, const Func &op = std::minus<T>()) {
    const int N = f.size();
    assert((N & (N - 1)) == 0 && "N must be a power of 2");
    for (int i = 1; i < N; i <<= 1) {
      for (int j = 0; j < N; ++j) {
        if (not(j & i)) f[j] = op(f[j], f[j ^ i]);
      }
    }
    return f;
  }
}  // namespace haar_lib
#line 5 "Mylib/Convolution/fast_zeta_transform_superset.cpp"

namespace haar_lib {
  template <typename T, typename Func = std::plus<T>>
  std::vector<T> fast_zeta_transform_superset(std::vector<T> f, const Func &op = std::plus<T>()) {
    const int N = f.size();
    assert((N & (N - 1)) == 0 && "N must be a power of 2");
    for (int i = 1; i < N; i <<= 1) {
      for (int j = 0; j < N; ++j) {
        if (not(j & i)) f[j] = op(f[j], f[j ^ i]);
      }
    }
    return f;
  }
}  // namespace haar_lib
#line 5 "Mylib/Convolution/convolution_and.cpp"

namespace haar_lib {
  template <typename T>
  std::vector<T> convolution_and(std::vector<T> f, std::vector<T> g) {
    f = fast_zeta_transform_superset(f);
    g = fast_zeta_transform_superset(g);
    for (size_t i = 0; i < f.size(); ++i) f[i] *= g[i];
    f = fast_mobius_transform_superset(f);
    return f;
  }
}  // namespace haar_lib

Back to top page