convolution/walsh_hadamard_transform.hpp

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

Required by

• convolution/convolution_xor.hpp

Verified with

• verify/yosupo_convolution/convolution_xor.test.cpp

Code

#ifndef KK2_CONVOLUTION_WALSH_HADAMARD_TRANSFORM_HPP
#define KK2_CONVOLUTION_WALSH_HADAMARD_TRANSFORM_HPP 1

#include <cassert>

namespace kk2 {

template <class FPS> void walsh_hadamard_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) {
                auto x = a[j], y = a[i ^ j];
                a[j] = -x + y, a[i ^ j] = x + y;
            }
        }
    }
}

template <class FPS> void inverse_walsh_hadamard_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) {
                auto x = a[j], y = a[i ^ j];
                a[j] = (-x + y) / 2, a[i ^ j] = (x + y) / 2;
            }
        }
    }
}

} // namespace kk2

#endif // KK2_CONVOLUTION_WALSH_HADAMARD_TRANSFORM_HPP

#line 1 "convolution/walsh_hadamard_transform.hpp"



#include <cassert>

namespace kk2 {

template <class FPS> void walsh_hadamard_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) {
                auto x = a[j], y = a[i ^ j];
                a[j] = -x + y, a[i ^ j] = x + y;
            }
        }
    }
}

template <class FPS> void inverse_walsh_hadamard_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) {
                auto x = a[j], y = a[i ^ j];
                a[j] = (-x + y) / 2, a[i ^ j] = (x + y) / 2;
            }
        }
    }
}

} // namespace kk2

Back to top page