Bitwise AND Convolution
(convolution/and_convolution.hpp)

• View this file on GitHub
• Last update: 2023-10-26 18:33:49+09:00
• Include: #include "convolution/and_convolution.hpp"

説明

長さ $2^N$ の整数列 $a$ と $b$ について、 $c_k = \sum_{i\& j=k} a_i b_j$ を求める。 $O(N 2^N)$

Depends on

• Superset Transform (Zeta / Möbius) (set_function/superset_transform.hpp)

Verified with

• test/convolution/Bitwise_And_Convolution.test.cpp

Code

#pragma once

#include <vector>

#include "../set_function/superset_transform.hpp"

namespace ebi {

template <class T>
std::vector<T> and_convolution(const std::vector<T> &a,
                               const std::vector<T> &b) {
    int n = a.size();
    auto ra = superset_zeta(a);
    auto rb = superset_zeta(b);
    for (int i = 0; i < n; i++) {
        ra[i] *= rb[i];
    }
    return superset_mobius(ra);
}

}  // namespace ebi

#line 2 "convolution/and_convolution.hpp"

#include <vector>

#line 2 "set_function/superset_transform.hpp"

#include <bit>
#include <cassert>
#line 6 "set_function/superset_transform.hpp"

namespace ebi {

template <class T> std::vector<T> superset_zeta(const std::vector<T> &a) {
    int n = std::bit_width(a.size()) - 1;
    assert((1 << n) == (int)a.size());
    std::vector<T> ra = a;
    for (int i = 0; i < n; i++) {
        int w = 1 << i;
        for (int p = 0; p < (1 << n); p += 2 * w) {
            for (int s = p; s < p + w; s++) {
                int t = s | w;
                ra[s] += ra[t];
            }
        }
    }
    return ra;
}

template <class T> std::vector<T> superset_mobius(const std::vector<T> &ra) {
    int n = std::bit_width(ra.size()) - 1;
    assert((1 << n) == (int)ra.size());
    std::vector<T> a = ra;
    for (int i = 0; i < n; i++) {
        int w = 1 << i;
        for (int p = 0; p < (1 << n); p += 2 * w) {
            for (int s = p; s < p + w; s++) {
                int t = s | w;
                a[s] -= a[t];
            }
        }
    }
    return a;
}

}  // namespace ebi
#line 6 "convolution/and_convolution.hpp"

namespace ebi {

template <class T>
std::vector<T> and_convolution(const std::vector<T> &a,
                               const std::vector<T> &b) {
    int n = a.size();
    auto ra = superset_zeta(a);
    auto rb = superset_zeta(b);
    for (int i = 0; i < n; i++) {
        ra[i] *= rb[i];
    }
    return superset_mobius(ra);
}

}  // namespace ebi

Back to top page