convolution/convolution_or.hpp

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

Depends on

• convolution/zeta_mobius_transfrom.hpp

Verified with

• verify/yosupo_convolution/convolution_or.test.cpp

Code

#ifndef KK2_CONVOLUTION_CONVOLUTION_OR_HPP
#define KK2_CONVOLUTION_CONVOLUTION_OR_HPP 1

#include <cassert>

#include "zeta_mobius_transfrom.hpp"

namespace kk2 {

template <class FPS> FPS convolution_or(FPS &a, const FPS &b) {
    assert(size(a) == size(b));
    int n = int(size(a)); // == int(size(b)
    if (!n) return {};
    assert((n & -n) == n); // n is a power of 2
    FPS c(b.begin(), b.end());

    subset_zeta_transform(a);
    subset_zeta_transform(c);
    for (int i = 0; i < n; i++) a[i] *= c[i];
    inverse_subset_zeta_transform(a);

    return a;
}

} // namespace kk2

#endif // KK2_CONVOLUTION_CONVOLUTION_OR_HPP

#line 1 "convolution/convolution_or.hpp"



#include <cassert>

#line 1 "convolution/zeta_mobius_transfrom.hpp"



#line 5 "convolution/zeta_mobius_transfrom.hpp"

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


#line 7 "convolution/convolution_or.hpp"

namespace kk2 {

template <class FPS> FPS convolution_or(FPS &a, const FPS &b) {
    assert(size(a) == size(b));
    int n = int(size(a)); // == int(size(b)
    if (!n) return {};
    assert((n & -n) == n); // n is a power of 2
    FPS c(b.begin(), b.end());

    subset_zeta_transform(a);
    subset_zeta_transform(c);
    for (int i = 0; i < n; i++) a[i] *= c[i];
    inverse_subset_zeta_transform(a);

    return a;
}

} // namespace kk2

Back to top page