Bitwise OR Convolution
(convolution/or_convolution.hpp)

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

説明

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

Depends on

• Subset Transform (Zeta / Möbius) (set_function/subset_transform.hpp)

Required by

• Chromatic Number (彩色数) (graph/chromatic_number.hpp)

Verified with

• test/convolution/Bitwise_OR_Convolution.test.cpp
• test/graph/Chromatic_Number.test.cpp

Code

#pragma once

#include "../set_function/subset_transform.hpp"

namespace ebi {

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

}  // namespace ebi

#line 2 "convolution/or_convolution.hpp"

#line 2 "set_function/subset_transform.hpp"

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

namespace ebi {

template <class T> std::vector<T> subset_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[t] += ra[s];
            }
        }
    }
    return ra;
}

template <class T> std::vector<T> subset_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[t] -= a[s];
            }
        }
    }
    return a;
}

}  // namespace ebi
#line 4 "convolution/or_convolution.hpp"

namespace ebi {

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

}  // namespace ebi

Back to top page