walsh_hadamard_transform
(src/math/walsh_hadamard_transform.hpp)

• View this file on GitHub
• Last update: 2024-11-09 01:34:39+09:00
• Include: #include "src/math/walsh_hadamard_transform.hpp"

walsh_hadamard_transform

void walsh_hadamard_transform(vector<T>& f, bool inv = false)

長さ $2^N$ の数列 $f$ の高速ウォルシュアダマール変換を計算します．
inv = true のとき，逆変換を計算します．

制約

• 数列 $f$ の長さは $2$ の累乗である．

計算量

• $O(2^N N)$

Depends on

• template (src/template/template.hpp)

Required by

• xor_convolution (src/convolution/xor_convolution.hpp)

Verified with

• verify/library_checker/convolution/bitwise_xor_convolution.test.cpp

Code

#pragma once
#include "../template/template.hpp"
template <typename T>
void walsh_hadamard_transform(vector<T>& f, const bool inv = false) {
    const int n = f.size();
    assert((n & (n - 1)) == 0);
    for(int i = 1; i < n; i <<= 1) {
        for(int j = 0; j < n; ++j) {
            if((j & i) == 0) {
                const T x = f[j], y = f[j | i];
                f[j] = x + y, f[j | i] = x - y;
            }
        }
    }
    if(inv) {
        if constexpr(is_integral<T>::value) {
            for(auto& x : f) x /= n;
        } else {
            const T invn = T(1) / T(f.size());
            for(auto& x : f) x *= invn;
        }
    }
}

#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/math/walsh_hadamard_transform.hpp"
template <typename T>
void walsh_hadamard_transform(vector<T>& f, const bool inv = false) {
    const int n = f.size();
    assert((n & (n - 1)) == 0);
    for(int i = 1; i < n; i <<= 1) {
        for(int j = 0; j < n; ++j) {
            if((j & i) == 0) {
                const T x = f[j], y = f[j | i];
                f[j] = x + y, f[j | i] = x - y;
            }
        }
    }
    if(inv) {
        if constexpr(is_integral<T>::value) {
            for(auto& x : f) x /= n;
        } else {
            const T invn = T(1) / T(f.size());
            for(auto& x : f) x *= invn;
        }
    }
}

Back to top page