convolution/zeta_mobius_transfrom.hpp

• View this file on GitHub
• Last update: 2025-01-05 04:43:56+09:00
• Include: #include "convolution/zeta_mobius_transfrom.hpp"

Required by

• convolution/convolution_and.hpp
• convolution/convolution_or.hpp

Verified with

• verify/yosupo_convolution/convolution_and.test.cpp
• verify/yosupo_convolution/convolution_or.test.cpp

Code

#ifndef KK2_CONVOLUTION_ZETA_MOBIUS_TRANSFORM_HPP
#define KK2_CONVOLUTION_ZETA_MOBIUS_TRANSFORM_HPP 1

#include <cassert>

namespace kk2 {

template <class FPS> void superset_zeta_transform(FPS &a) {
    int n = int(a.size());
    if (!n) return;
    assert((n & -n) == n);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((i & j) == 0) a[j] += a[i ^ j];
        }
    }
}

template <class FPS> void inverse_superset_zeta_transform(FPS &a) {
    int n = int(a.size());
    if (!n) return;
    assert((n & -n) == n);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((i & j) == 0) a[j] -= a[i ^ j];
        }
    }
}

template <class FPS> void subset_zeta_transform(FPS &a) {
    int n = int(a.size());
    if (!n) return;
    assert((n & -n) == n);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((i & j) != 0) a[j] += a[i ^ j];
        }
    }
}

template <class FPS> void inverse_subset_zeta_transform(FPS &a) {
    int n = int(a.size());
    if (!n) return;
    assert((n & -n) == n);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((i & j) != 0) a[j] -= a[i ^ j];
        }
    }
}

} // namespace kk2

#endif // KK2_CONVOLUTION_ZETA_MOBIUS_TRANSFORM_HPP

#line 1 "convolution/zeta_mobius_transfrom.hpp"



#include <cassert>

namespace kk2 {

template <class FPS> void superset_zeta_transform(FPS &a) {
    int n = int(a.size());
    if (!n) return;
    assert((n & -n) == n);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((i & j) == 0) a[j] += a[i ^ j];
        }
    }
}

template <class FPS> void inverse_superset_zeta_transform(FPS &a) {
    int n = int(a.size());
    if (!n) return;
    assert((n & -n) == n);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((i & j) == 0) a[j] -= a[i ^ j];
        }
    }
}

template <class FPS> void subset_zeta_transform(FPS &a) {
    int n = int(a.size());
    if (!n) return;
    assert((n & -n) == n);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((i & j) != 0) a[j] += a[i ^ j];
        }
    }
}

template <class FPS> void inverse_subset_zeta_transform(FPS &a) {
    int n = int(a.size());
    if (!n) return;
    assert((n & -n) == n);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((i & j) != 0) a[j] -= a[i ^ j];
        }
    }
}

} // namespace kk2

Back to top page