Bitwise And Convolution (Bitwise-AND畳み込み) (math/fft/bitwise-and-convolution.hpp)

• View this file on GitHub
• Last update: 2024-04-27 01:27:28+09:00
• Include: #include "math/fft/bitwise-and-convolution.hpp"

Depends on

• Superset Zeta/Moebius Transform (上位集合のゼータ/メビウス変換) (math/fft/superset-zeta-moebius-transform.hpp)

Verified with

• test/verify/yosupo-bitwise-and-convolution.test.cpp

Code

#include "superset-zeta-moebius-transform.hpp"

/**
 * @brief Bitwise And Convolution (Bitwise-AND畳み込み)
 */
template <typename T>
vector<T> bitwise_and_convolution(vector<T> f, vector<T> g) {
  const int n = (int)f.size();
  assert(f.size() == g.size());
  assert((n & (n - 1)) == 0);
  superset_zeta_transform(f);
  superset_zeta_transform(g);
  for (int i = 0; i < n; i++) f[i] *= g[i];
  superset_moebius_transform(f);
  return f;
}

#line 1 "math/fft/superset-zeta-moebius-transform.hpp"
/**
 * @brief Superset Zeta/Moebius Transform (上位集合のゼータ/メビウス変換)
 */
template <typename T>
void superset_zeta_transform(vector<T> &f) {
  const int n = (int)f.size();
  assert((n & (n - 1)) == 0);
  for (int i = 1; i < n; i <<= 1) {
    for (int j = 0; j < n; j += i << 1) {
      for (int k = 0; k < i; k++) {
        f[j + k] += f[j + k + i];
      }
    }
  }
}

template <typename T>
void superset_moebius_transform(vector<T> &f) {
  const int n = (int)f.size();
  assert((n & (n - 1)) == 0);
  for (int i = 1; i < n; i <<= 1) {
    for (int j = 0; j < n; j += i << 1) {
      for (int k = 0; k < i; k++) {
        f[j + k] -= f[j + k + i];
      }
    }
  }
}
#line 2 "math/fft/bitwise-and-convolution.hpp"

/**
 * @brief Bitwise And Convolution (Bitwise-AND畳み込み)
 */
template <typename T>
vector<T> bitwise_and_convolution(vector<T> f, vector<T> g) {
  const int n = (int)f.size();
  assert(f.size() == g.size());
  assert((n & (n - 1)) == 0);
  superset_zeta_transform(f);
  superset_zeta_transform(g);
  for (int i = 0; i < n; i++) f[i] *= g[i];
  superset_moebius_transform(f);
  return f;
}

Back to top page