Bitwise AND/OR Convolution
(math/set/and_or_convolution.hpp)

• View this file on GitHub
• Last update: 2024-01-08 17:31:43+09:00
• Include: #include "math/set/and_or_convolution.hpp"

Depends on

• Fast Zeta/Möbius Transform (math/set/zeta_moebius_transform.hpp)

Verified with

• test/yosupo/bitwise_and_convolution.test.cpp

Code

#pragma once
#include <bit>
#include <vector>

#include "zeta_moebius_transform.hpp"

/**
 * @brief Bitwise AND/OR Convolution
 */

template <typename T>
std::vector<T> and_convolution(std::vector<T> a, std::vector<T> b) {
    const int n = std::bit_ceil(std::max(a.size(), b.size()));
    a.resize(n);
    b.resize(n);
    superset_fzt(a);
    superset_fzt(b);
    for (int i = 0; i < n; ++i) a[i] *= b[i];
    superset_fmt(a);
    return a;
}

template <typename T>
std::vector<T> or_convolution(std::vector<T> a, std::vector<T> b) {
    const int n = std::bit_ceil(std::max(a.size(), b.size()));
    a.resize(n);
    b.resize(n);
    subset_fzt(a);
    subset_fzt(b);
    for (int i = 0; i < n; ++i) a[i] *= b[i];
    subset_fmt(a);
    return a;
}

#line 2 "math/set/and_or_convolution.hpp"
#include <bit>
#include <vector>

#line 3 "math/set/zeta_moebius_transform.hpp"
#include <cassert>
#line 5 "math/set/zeta_moebius_transform.hpp"

template <typename T>
void superset_fzt(std::vector<T>& a) {
    assert(std::has_single_bit(a.size()));
    const int n = a.size();
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; ++j) {
            if (!(j & i)) a[j] += a[j | i];
        }
    }
}

template <typename T>
void superset_fmt(std::vector<T>& a) {
    assert(std::has_single_bit(a.size()));
    const int n = a.size();
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; ++j) {
            if (!(j & i)) a[j] -= a[j | i];
        }
    }
}

template <typename T>
void subset_fzt(std::vector<T>& a) {
    assert(std::has_single_bit(a.size()));
    const int n = a.size();
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; ++j) {
            if (!(j & i)) a[j | i] += a[j];
        }
    }
}

template <typename T>
void subset_fmt(std::vector<T>& a) {
    assert(std::has_single_bit(a.size()));
    const int n = a.size();
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; ++j) {
            if (!(j & i)) a[j | i] -= a[j];
        }
    }
}
#line 6 "math/set/and_or_convolution.hpp"

/**
 * @brief Bitwise AND/OR Convolution
 */

template <typename T>
std::vector<T> and_convolution(std::vector<T> a, std::vector<T> b) {
    const int n = std::bit_ceil(std::max(a.size(), b.size()));
    a.resize(n);
    b.resize(n);
    superset_fzt(a);
    superset_fzt(b);
    for (int i = 0; i < n; ++i) a[i] *= b[i];
    superset_fmt(a);
    return a;
}

template <typename T>
std::vector<T> or_convolution(std::vector<T> a, std::vector<T> b) {
    const int n = std::bit_ceil(std::max(a.size(), b.size()));
    a.resize(n);
    b.resize(n);
    subset_fzt(a);
    subset_fzt(b);
    for (int i = 0; i < n; ++i) a[i] *= b[i];
    subset_fmt(a);
    return a;
}

Back to top page