Hadamard Transform
(set_function/hadamard_transform.hpp)

• View this file on GitHub
• Last update: 2023-05-16 01:22:44+09:00
• Include: #include "set_function/hadamard_transform.hpp"

説明

アダマール変換を行う。 $O(N\log N)$

Required by

• Bitwise XOR Convolution (convolution/xor_convolution.hpp)

Verified with

• test/convolution/Bitwise_Xor_Convolution.test.cpp

Code

#pragma once

#include <vector>

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 2 "set_function/hadamard_transform.hpp"

#include <vector>

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

Back to top page