transform/superset_zeta.hpp

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

Required by

• convolution/and.hpp

Verified with

• test/convolution/bitwise_and_convolution.test.cpp

Code

#ifndef SUPERSET_ZETA_HPP
#define SUPERSET_ZETA_HPP

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

template <typename T> void superset_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 ^ (1 << i)] += f[s];
            }
        }
    }
}

#endif // SUPERSET_ZETA_HPP

#line 1 "transform/superset_zeta.hpp"



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

template <typename T> void superset_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 ^ (1 << i)] += f[s];
            }
        }
    }
}

Back to top page