This documentation is automatically generated by online-judge-tools/verification-helper
#include "src/math/convolution/fast-walsh-hadamard-transform.hpp"
#pragma once
#include "src/cpp-template/header/rep.hpp"
#include "src/cpp-template/header/size-alias.hpp"
#include <cassert>
#include <vector>
namespace luz {
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: rep(0, i)) {
op(f[j + k], f[j + k + i]);
}
j += i << 1;
}
i <<= 1;
}
}
} // namespace luz
#line 2 "src/math/convolution/fast-walsh-hadamard-transform.hpp"
#line 2 "src/cpp-template/header/rep.hpp"
#line 2 "src/cpp-template/header/size-alias.hpp"
#include <cstddef>
namespace luz {
using isize = std::ptrdiff_t;
using usize = std::size_t;
} // namespace luz
#line 4 "src/cpp-template/header/rep.hpp"
#include <algorithm>
namespace luz {
struct rep {
struct itr {
usize i;
constexpr itr(const usize i) noexcept: i(i) {}
void operator++() noexcept {
++i;
}
constexpr usize operator*() const noexcept {
return i;
}
constexpr bool operator!=(const itr x) const noexcept {
return i != x.i;
}
};
const itr f, l;
constexpr rep(const usize f, const usize l) noexcept
: f(std::min(f, l)),
l(l) {}
constexpr auto begin() const noexcept {
return f;
}
constexpr auto end() const noexcept {
return l;
}
};
struct rrep {
struct itr {
usize i;
constexpr itr(const usize i) noexcept: i(i) {}
void operator++() noexcept {
--i;
}
constexpr usize operator*() const noexcept {
return i;
}
constexpr bool operator!=(const itr x) const noexcept {
return i != x.i;
}
};
const itr f, l;
constexpr rrep(const usize f, const usize l) noexcept
: f(l - 1),
l(std::min(f, l) - 1) {}
constexpr auto begin() const noexcept {
return f;
}
constexpr auto end() const noexcept {
return l;
}
};
} // namespace luz
#line 5 "src/math/convolution/fast-walsh-hadamard-transform.hpp"
#include <cassert>
#include <vector>
namespace luz {
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: rep(0, i)) {
op(f[j + k], f[j + k + i]);
}
j += i << 1;
}
i <<= 1;
}
}
} // namespace luz