library/set-function/walsh-hadamard-transform.hpp

• View this file on GitHub
• Last update: 2022-07-21 16:12:33-04:00
• Include: #include "library/set-function/walsh-hadamard-transform.hpp"

Verified with

• verify/yosupo/yosupo-bitwise_xor_convolution.test.cpp

Code

#pragma once

template <class T> 
void walsh_hadamard_transformation(std::vector<T>& f, bool inverse = false) {
	int n = (int)f.size();
	for (int i = 1; i < n; i <<= 1) {
		for (int j = 0; j < n; ++j) {
			if ((j & i) == 0) {
				T x = f[j], y = f[j | i];
				f[j] = x + y;
				f[j | i] = x - y;
			}
		}
	}
	if (inverse) {
		if constexpr(std::is_integral<T>::value) {
			for (auto& x : f) x /= n;
		} else {
			T divide = T(1) / T(f.size());
			for (auto& x : f) x *= divide;
		}
	}
}

template <class T> 
void walsh_hadamard_transformation(std::vector<T>& f, bool inverse = false) {
	int n = (int)f.size();
	for (int i = 1; i < n; i <<= 1) {
		for (int j = 0; j < n; ++j) {
			if ((j & i) == 0) {
				T x = f[j], y = f[j | i];
				f[j] = x + y;
				f[j | i] = x - y;
			}
		}
	}
	if (inverse) {
		if constexpr(std::is_integral<T>::value) {
			for (auto& x : f) x /= n;
		} else {
			T divide = T(1) / T(f.size());
			for (auto& x : f) x *= divide;
		}
	}
}

Back to top page