高速WalshHadamard変換
(library/polynomial/fft/fast_walsh_hadamard_transform.hpp)

• View this file on GitHub
• Last update: 2026-01-19 13:29:11+09:00
• Include: #include "library/polynomial/fft/fast_walsh_hadamard_transform.hpp"

高速WalshHadamard変換

詳しい説明

できること

• 行列とベクトルの積を高速に計算するための変換

計算量

$O(NlogN)$

使い方

fast_walsh_hadamard_transform(f, false);

Required by

• Bitwise畳み込みXOR (library/polynomial/fft/convolution_bitwise_xor.hpp)

Verified with

• Bitwise畳み込みXORのテスト (tests/polynomial.fft.convolution_bitwise_xor.test.cpp)

Code

#pragma once
template <typename T>
void fast_walsh_hadamard_transform(vector<T> &f, bool inv = false) {
    const int n = (int)f.size();
    assert((n & (n - 1)) == 0);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j += i << 1) {
            for (int k = 0; k < i; k++) {
                T s = f[j + k], t = f[j + k + i];
                f[j + k] = s + t;
                f[j + k + i] = s - t;
            }
        }
    }
    if (inv) {
        T inv_n = T(1) / n;
        for (auto &x : f) x *= inv_n;
    }
}

#line 2 "library/polynomial/fft/fast_walsh_hadamard_transform.hpp"
template <typename T>
void fast_walsh_hadamard_transform(vector<T> &f, bool inv = false) {
    const int n = (int)f.size();
    assert((n & (n - 1)) == 0);
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j += i << 1) {
            for (int k = 0; k < i; k++) {
                T s = f[j + k], t = f[j + k + i];
                f[j + k] = s + t;
                f[j + k + i] = s - t;
            }
        }
    }
    if (inv) {
        T inv_n = T(1) / n;
        for (auto &x : f) x *= inv_n;
    }
}

Back to top page