transform/subset_zeta.hpp

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

Required by

• convolution/or.hpp

Verified with

• test/convolution/bitwise_or_convolution.test.cpp
• test/transform/chayas.test.cpp

Code

#ifndef SUBSET_ZETA_HPP
#define SUBSET_ZETA_HPP

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

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)];
            }
        }
    }
}

#endif // SUBSET_ZETA_HPP

#line 1 "transform/subset_zeta.hpp"



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

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)];
            }
        }
    }
}

Back to top page