This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/Library
#include "convolution/xor_convolution.hpp"
長さ $2^N$ の整数列 $a$ と $b$ について、 $c_k = \sum_{i\oplus j=k} a_i b_j$ を求める。 $O(N 2^N)$
#pragma once #include <cassert> #include <vector> #include "../set_function/hadamard_transform.hpp" namespace ebi { template <class T> std::vector<T> xor_convolution(const std::vector<T> &a, const std::vector<T> &b) { assert(a.size() == b.size()); auto ta = hadamard_transform(a); auto tb = hadamard_transform(b); for (int i = 0; i < (int)a.size(); i++) { ta[i] *= tb[i]; } return hadamard_transform(ta, true); } } // namespace ebi
#line 2 "convolution/xor_convolution.hpp" #include <cassert> #include <vector> #line 2 "set_function/hadamard_transform.hpp" #line 4 "set_function/hadamard_transform.hpp" namespace ebi { template <class T> std::vector<T> hadamard_transform(std::vector<T> f, bool inverse = false) { int n = f.size(); for (int i = 1; i < n; i <<= 1) { for (int j = 0; j < n; j++) { if ((i & j) == 0) { T x = f[j], y = f[j | i]; f[j] = x + y; f[j | i] = x - y; } } } if (inverse) { for (auto& x : f) { x /= T(n); } } return f; } } // namespace ebi #line 7 "convolution/xor_convolution.hpp" namespace ebi { template <class T> std::vector<T> xor_convolution(const std::vector<T> &a, const std::vector<T> &b) { assert(a.size() == b.size()); auto ta = hadamard_transform(a); auto tb = hadamard_transform(b); for (int i = 0; i < (int)a.size(); i++) { ta[i] *= tb[i]; } return hadamard_transform(ta, true); } } // namespace ebi