Bitwise XOR Convolution
(convolution/xor_convolution.hpp)

• View this file on GitHub
• Last update: 2023-05-16 13:40:06+09:00
• Include: #include "convolution/xor_convolution.hpp"

説明

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

Depends on

• Hadamard Transform (set_function/hadamard_transform.hpp)

Verified with

• test/convolution/Bitwise_Xor_Convolution.test.cpp

Code

#pragma once

#include <cassert>
#include <vector>

#include "../set_function/hadamard_transform.hpp"

namespace ebi {

template <class T>
std::vector<T> xor_convolution(const std::vector<T> &a,
                               const std::vector<T> &b) {
    assert(a.size() == b.size());
    auto ta = hadamard_transform(a);
    auto tb = hadamard_transform(b);
    for (int i = 0; i < (int)a.size(); i++) {
        ta[i] *= tb[i];
    }
    return hadamard_transform(ta, true);
}

}  // namespace ebi

#line 2 "convolution/xor_convolution.hpp"

#include <cassert>
#include <vector>

#line 2 "set_function/hadamard_transform.hpp"

#line 4 "set_function/hadamard_transform.hpp"

namespace ebi {

template <class T>
std::vector<T> hadamard_transform(std::vector<T> f, bool inverse = false) {
    int n = f.size();
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j++) {
            if ((i & j) == 0) {
                T x = f[j], y = f[j | i];
                f[j] = x + y;
                f[j | i] = x - y;
            }
        }
    }
    if (inverse) {
        for (auto& x : f) {
            x /= T(n);
        }
    }
    return f;
}

}  // namespace ebi
#line 7 "convolution/xor_convolution.hpp"

namespace ebi {

template <class T>
std::vector<T> xor_convolution(const std::vector<T> &a,
                               const std::vector<T> &b) {
    assert(a.size() == b.size());
    auto ta = hadamard_transform(a);
    auto tb = hadamard_transform(b);
    for (int i = 0; i < (int)a.size(); i++) {
        ta[i] *= tb[i];
    }
    return hadamard_transform(ta, true);
}

}  // namespace ebi

Back to top page