convolution/or.hpp

• View this file on GitHub
• Last update: 2026-07-15 17:18:58+00:00
• Include: #include "convolution/or.hpp"

Depends on

• transform/subset_mobius.hpp
• transform/subset_zeta.hpp

Verified with

• test/convolution/bitwise_or_convolution.test.cpp

Code

#ifndef OR_HPP
#define OR_HPP

#include "transform/subset_mobius.hpp"
#include "transform/subset_zeta.hpp"
#include <cassert>
#include <vector>

template <typename T> std::vector<T> or_convolution(std::vector<T> a, std::vector<T> b) {
    assert(a.size() == b.size());
    subset_zeta_transform(a);
    subset_zeta_transform(b);
    for (auto i = 0; i < int(a.size()); ++i) {
        a[i] *= b[i];
    }
    subset_mobius_transform(a);
    return a;
}

#endif // OR_HPP

#line 1 "convolution/or.hpp"



#line 1 "transform/subset_mobius.hpp"



#include <bit>
#include <cassert>
#include <vector>

template <typename T> void subset_mobius_transform(std::vector<T> &g) {
    assert(std::has_single_bit(g.size()));
    auto n = int(std::countr_zero(g.size()));
    for (auto i = 0; i < n; ++i) {
        for (auto s = 0; s < (1 << n); ++s) {
            if (s & (1 << i)) {
                g[s] -= g[s ^ (1 << i)];
            }
        }
    }
}


#line 1 "transform/subset_zeta.hpp"



#line 7 "transform/subset_zeta.hpp"

template <typename T> void subset_zeta_transform(std::vector<T> &f) {
    assert(std::has_single_bit(f.size()));
    auto n = int(std::countr_zero(f.size()));
    for (auto i = 0; i < n; ++i) {
        for (auto s = 0; s < (1 << n); ++s) {
            if (s & (1 << i)) {
                f[s] += f[s ^ (1 << i)];
            }
        }
    }
}


#line 8 "convolution/or.hpp"

template <typename T> std::vector<T> or_convolution(std::vector<T> a, std::vector<T> b) {
    assert(a.size() == b.size());
    subset_zeta_transform(a);
    subset_zeta_transform(b);
    for (auto i = 0; i < int(a.size()); ++i) {
        a[i] *= b[i];
    }
    subset_mobius_transform(a);
    return a;
}

Back to top page