This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub Luzhiled/syakyo-library
#include "src/math/convolution/bitwise-and-convolution.hpp"
#pragma once #include "src/cpp-template/header/size-alias.hpp" #include "src/math/convolution/fast-walsh-hadamard-transform.hpp" #include <cassert> #include <vector> namespace luz { // length of f and g must be 2^k template < typename T > std::vector< T > bitwise_and_convolution(std::vector< T > f, std::vector< T > g) { assert(f.size() == g.size()); auto zeta = [](T &lo, T hi) { return lo += hi; }; auto mobius = [](T &lo, T hi) { return lo -= hi; }; fast_walsh_hadamard_transform(f, zeta); fast_walsh_hadamard_transform(g, zeta); for (usize i = 0; i < f.size(); i++) { f[i] *= g[i]; } fast_walsh_hadamard_transform(f, mobius); return f; } } // namespace luz
#line 2 "src/math/convolution/bitwise-and-convolution.hpp" #line 2 "src/cpp-template/header/size-alias.hpp" #include <cstddef> namespace luz { using isize = std::ptrdiff_t; using usize = std::size_t; } #line 2 "src/math/convolution/fast-walsh-hadamard-transform.hpp" #line 4 "src/math/convolution/fast-walsh-hadamard-transform.hpp" #include <cassert> #include <vector> namespace luz { // length of f must be 2^k template < typename T, typename F > void fast_walsh_hadamard_transform(std::vector< T > &f, F op) { const usize n = f.size(); assert((n & (n - 1)) == 0); usize i = 1; while (i < n) { usize j = 0; while (j < n) { for (usize k = 0; k < i; k++) { op(f[j + k], f[j + k + i]); } j += i << 1; } i <<= 1; } } } // namespace luz #line 5 "src/math/convolution/bitwise-and-convolution.hpp" #line 8 "src/math/convolution/bitwise-and-convolution.hpp" namespace luz { // length of f and g must be 2^k template < typename T > std::vector< T > bitwise_and_convolution(std::vector< T > f, std::vector< T > g) { assert(f.size() == g.size()); auto zeta = [](T &lo, T hi) { return lo += hi; }; auto mobius = [](T &lo, T hi) { return lo -= hi; }; fast_walsh_hadamard_transform(f, zeta); fast_walsh_hadamard_transform(g, zeta); for (usize i = 0; i < f.size(); i++) { f[i] *= g[i]; } fast_walsh_hadamard_transform(f, mobius); return f; } } // namespace luz