sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#include "convolution/xor_convolution.hpp"
#pragma once #include <bit> #include <vector> #include "walsh_hadamard_transform.hpp" /** * @brief Bitwise XOR Convolution */ template <typename T> std::vector<T> xor_convolution(std::vector<T> a, std::vector<T> b) { const int n = std::bit_ceil(std::max(a.size(), b.size())); a.resize(n); b.resize(n); fwht(a); fwht(b); for (int i = 0; i < n; ++i) a[i] *= b[i]; ifwht(a); return a; }
#line 2 "convolution/xor_convolution.hpp" #include <bit> #include <vector> #line 3 "convolution/walsh_hadamard_transform.hpp" #include <cassert> #line 5 "convolution/walsh_hadamard_transform.hpp" template <typename T> void fwht(std::vector<T>& a) { assert(std::has_single_bit(a.size())); const int n = a.size(); for (int h = 1; h < n; h <<= 1) { for (int i = 0; i < n; i += h << 1) { for (int j = i; j < i + h; ++j) { T x = a[j], y = a[j | h]; a[j] = x + y; a[j | h] = x - y; } } } } template <typename T> void ifwht(std::vector<T>& a) { assert(std::has_single_bit(a.size())); const int n = a.size(); const T inv2 = T(1) / 2; for (int h = 1; h < n; h <<= 1) { for (int i = 0; i < n; i += h << 1) { for (int j = i; j < i + h; ++j) { T x = a[j], y = a[j | h]; a[j] = (x + y) * inv2; a[j | h] = (x - y) * inv2; } } } } #line 6 "convolution/xor_convolution.hpp" /** * @brief Bitwise XOR Convolution */ template <typename T> std::vector<T> xor_convolution(std::vector<T> a, std::vector<T> b) { const int n = std::bit_ceil(std::max(a.size(), b.size())); a.resize(n); b.resize(n); fwht(a); fwht(b); for (int i = 0; i < n; ++i) a[i] *= b[i]; ifwht(a); return a; }