This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#include "library/transform/kronecker.hpp"
#ifndef SUISEN_KRONECKER_TRANSFORM #define SUISEN_KRONECKER_TRANSFORM #include <cassert> #include <type_traits> #include <vector> #include "library/util/step_view.hpp" #include "library/util/default_operator.hpp" namespace suisen::kronecker_transform { namespace internal { int log(int d, int n) { int l = 0, p = 1; while (p < n) p *= d, ++l; assert(p == n); return l; } } // trans: (dimension id, std::vector<T>&) -> void template <typename T, typename Transform, std::enable_if_t<std::is_invocable_v<Transform, int, StepView<std::vector<T>>>, std::nullptr_t> = nullptr> void transform(std::vector<T>& f, const std::vector<int>& dims, const Transform& trans) { const int n = f.size(), m = dims.size(); { int p = 1; for (int d : dims) p *= d; assert(p == n); } for (int i = 0, block = 1; i < m; ++i) { const int next_block = block * dims[i]; for (int l = 0; l < n; l += next_block) { for (int offset = l; offset < l + block; ++offset) { trans(i, StepView{ f, offset, block, dims[i] }); } } block = next_block; } } // trans: (std::vector<T>&) -> void template <typename T, typename Transform, std::enable_if_t<std::is_invocable_v<Transform, StepView<std::vector<T>>>, std::nullptr_t> = nullptr> void transform(std::vector<T>& f, int d, const Transform& trans) { transform(f, std::vector<int>(internal::log(d, f.size()), d), [&trans](int, StepView<std::vector<T>> view) { trans(view); }); } template <typename T, auto add = default_operator::add<T>> void sub_zeta(std::vector<T>& f, const std::vector<int>& dims) { transform( f, dims, [&](int, const StepView<std::vector<T>>& f) { for (size_t i = 1; i < f.size(); ++i) f[i] = add(f[i], f[i - 1]); } ); } template <typename T, auto add = default_operator::add<T>> void sub_zeta(std::vector<T>& f, int d) { sub_zeta<T, add>(f, std::vector<int>(internal::log(d, f.size()), d)); } template <typename T, auto sub = default_operator::sub<T>> void sub_mobius(std::vector<T>& f, const std::vector<int>& dims) { transform( f, dims, [&](int, const StepView<std::vector<T>>& f) { for (size_t i = f.size() - 1; i > 0; --i) f[i] = sub(f[i], f[i - 1]); } ); } template <typename T, auto sub = default_operator::sub<T>> void sub_mobius(std::vector<T>& f, int d) { sub_mobius<T, sub>(f, std::vector<int>(internal::log(d, f.size()), d)); } template <typename T, auto add = default_operator::add<T>> void sup_zeta(std::vector<T>& f, const std::vector<int>& dims) { transform( f, dims, [&](int, const StepView<std::vector<T>>& f) { for (size_t i = f.size() - 1; i > 0; --i) f[i - 1] = add(f[i - 1], f[i]); } ); } template <typename T, auto add = default_operator::add<T>> void sup_zeta(std::vector<T>& f, int d) { sup_zeta<T, add>(f, std::vector<int>(internal::log(d, f.size()), d)); } template <typename T, auto sub = default_operator::sub<T>> void sup_mobius(std::vector<T>& f, const std::vector<int>& dims) { transform( f, dims, [&](int, const StepView<std::vector<T>>& f) { for (size_t i = 1; i < f.size(); ++i) f[i - 1] = sub(f[i - 1], f[i]); } ); } template <typename T, auto sub = default_operator::sub<T>> void sup_mobius(std::vector<T>& f, int d) { sup_mobius<T, sub>(f, std::vector<int>(internal::log(d, f.size()), d)); } } // namespace suisen::kronecker_transform #endif // SUISEN_KRONECKER_TRANSFORM
#line 1 "library/transform/kronecker.hpp" #include <cassert> #include <type_traits> #include <vector> #line 1 "library/util/step_view.hpp" #include <iterator> namespace suisen { template <typename RandomAccessIterator> struct StepIterator { using difference_type = typename std::iterator_traits<RandomAccessIterator>::difference_type; using value_type = typename std::iterator_traits<RandomAccessIterator>::value_type; using pointer = typename std::iterator_traits<RandomAccessIterator>::pointer; using reference = typename std::iterator_traits<RandomAccessIterator>::reference; using iterator_category = typename std::iterator_traits<RandomAccessIterator>::iterator_category; static_assert(std::is_same_v<iterator_category, std::random_access_iterator_tag>); StepIterator(const RandomAccessIterator &it, int step) : _it(it), _step(step) {} StepIterator& operator++() { return _it += _step, *this; } StepIterator& operator--() { return _it -= _step, *this; } StepIterator operator++(int) { StepIterator ret = *this; ++(*this); return ret; } StepIterator operator--(int) { StepIterator ret = *this; --(*this); return ret; } StepIterator& operator+=(difference_type dif) { return _it += dif * _step, *this; } StepIterator& operator-=(difference_type dif) { return _it -= dif * _step, *this; } friend StepIterator operator+(StepIterator it, difference_type dif) { it += dif; return it; } friend StepIterator operator+(difference_type dif, StepIterator it) { it += dif; return it; } friend StepIterator operator-(StepIterator it, difference_type dif) { it -= dif; return it; } friend difference_type operator-(const StepIterator &lhs, const StepIterator &rhs) { return (lhs._it - rhs._it) / lhs._step; } reference operator[](difference_type i) const { return _it[i * _step]; } reference operator*() const { return *_it; } friend bool operator==(const StepIterator &lhs, const StepIterator &rhs) { return lhs._it == rhs._it; } friend bool operator!=(const StepIterator &lhs, const StepIterator &rhs) { return lhs._it != rhs._it; } friend bool operator< (const StepIterator &lhs, const StepIterator &rhs) { return lhs._it < rhs._it; } friend bool operator<=(const StepIterator &lhs, const StepIterator &rhs) { return lhs._it <= rhs._it; } friend bool operator> (const StepIterator &lhs, const StepIterator &rhs) { return lhs._it > rhs._it; } friend bool operator>=(const StepIterator &lhs, const StepIterator &rhs) { return lhs._it >= rhs._it; } private: RandomAccessIterator _it; int _step; }; template <typename RandomAccesibleContainer> struct StepView { using iterator = typename RandomAccesibleContainer::iterator; using value_type = typename RandomAccesibleContainer::value_type; using reference = typename RandomAccesibleContainer::reference; StepView(RandomAccesibleContainer& dat, int start, int step, int size) : _start(dat.begin() + start, step), _size(size) {} std::size_t size() const { return _size; } reference operator[](std::size_t k) const { return _start[k]; } private: StepIterator<iterator> _start; std::size_t _size; }; } // namespace suisen #line 1 "library/util/default_operator.hpp" namespace suisen { namespace default_operator { template <typename T> auto zero() -> decltype(T { 0 }) { return T { 0 }; } template <typename T> auto one() -> decltype(T { 1 }) { return T { 1 }; } template <typename T> auto add(const T &x, const T &y) -> decltype(x + y) { return x + y; } template <typename T> auto sub(const T &x, const T &y) -> decltype(x - y) { return x - y; } template <typename T> auto mul(const T &x, const T &y) -> decltype(x * y) { return x * y; } template <typename T> auto div(const T &x, const T &y) -> decltype(x / y) { return x / y; } template <typename T> auto mod(const T &x, const T &y) -> decltype(x % y) { return x % y; } template <typename T> auto neg(const T &x) -> decltype(-x) { return -x; } template <typename T> auto inv(const T &x) -> decltype(one<T>() / x) { return one<T>() / x; } } // default_operator namespace default_operator_noref { template <typename T> auto zero() -> decltype(T { 0 }) { return T { 0 }; } template <typename T> auto one() -> decltype(T { 1 }) { return T { 1 }; } template <typename T> auto add(T x, T y) -> decltype(x + y) { return x + y; } template <typename T> auto sub(T x, T y) -> decltype(x - y) { return x - y; } template <typename T> auto mul(T x, T y) -> decltype(x * y) { return x * y; } template <typename T> auto div(T x, T y) -> decltype(x / y) { return x / y; } template <typename T> auto mod(T x, T y) -> decltype(x % y) { return x % y; } template <typename T> auto neg(T x) -> decltype(-x) { return -x; } template <typename T> auto inv(T x) -> decltype(one<T>() / x) { return one<T>() / x; } } // default_operator } // namespace suisen #line 10 "library/transform/kronecker.hpp" namespace suisen::kronecker_transform { namespace internal { int log(int d, int n) { int l = 0, p = 1; while (p < n) p *= d, ++l; assert(p == n); return l; } } // trans: (dimension id, std::vector<T>&) -> void template <typename T, typename Transform, std::enable_if_t<std::is_invocable_v<Transform, int, StepView<std::vector<T>>>, std::nullptr_t> = nullptr> void transform(std::vector<T>& f, const std::vector<int>& dims, const Transform& trans) { const int n = f.size(), m = dims.size(); { int p = 1; for (int d : dims) p *= d; assert(p == n); } for (int i = 0, block = 1; i < m; ++i) { const int next_block = block * dims[i]; for (int l = 0; l < n; l += next_block) { for (int offset = l; offset < l + block; ++offset) { trans(i, StepView{ f, offset, block, dims[i] }); } } block = next_block; } } // trans: (std::vector<T>&) -> void template <typename T, typename Transform, std::enable_if_t<std::is_invocable_v<Transform, StepView<std::vector<T>>>, std::nullptr_t> = nullptr> void transform(std::vector<T>& f, int d, const Transform& trans) { transform(f, std::vector<int>(internal::log(d, f.size()), d), [&trans](int, StepView<std::vector<T>> view) { trans(view); }); } template <typename T, auto add = default_operator::add<T>> void sub_zeta(std::vector<T>& f, const std::vector<int>& dims) { transform( f, dims, [&](int, const StepView<std::vector<T>>& f) { for (size_t i = 1; i < f.size(); ++i) f[i] = add(f[i], f[i - 1]); } ); } template <typename T, auto add = default_operator::add<T>> void sub_zeta(std::vector<T>& f, int d) { sub_zeta<T, add>(f, std::vector<int>(internal::log(d, f.size()), d)); } template <typename T, auto sub = default_operator::sub<T>> void sub_mobius(std::vector<T>& f, const std::vector<int>& dims) { transform( f, dims, [&](int, const StepView<std::vector<T>>& f) { for (size_t i = f.size() - 1; i > 0; --i) f[i] = sub(f[i], f[i - 1]); } ); } template <typename T, auto sub = default_operator::sub<T>> void sub_mobius(std::vector<T>& f, int d) { sub_mobius<T, sub>(f, std::vector<int>(internal::log(d, f.size()), d)); } template <typename T, auto add = default_operator::add<T>> void sup_zeta(std::vector<T>& f, const std::vector<int>& dims) { transform( f, dims, [&](int, const StepView<std::vector<T>>& f) { for (size_t i = f.size() - 1; i > 0; --i) f[i - 1] = add(f[i - 1], f[i]); } ); } template <typename T, auto add = default_operator::add<T>> void sup_zeta(std::vector<T>& f, int d) { sup_zeta<T, add>(f, std::vector<int>(internal::log(d, f.size()), d)); } template <typename T, auto sub = default_operator::sub<T>> void sup_mobius(std::vector<T>& f, const std::vector<int>& dims) { transform( f, dims, [&](int, const StepView<std::vector<T>>& f) { for (size_t i = 1; i < f.size(); ++i) f[i - 1] = sub(f[i - 1], f[i]); } ); } template <typename T, auto sub = default_operator::sub<T>> void sup_mobius(std::vector<T>& f, int d) { sup_mobius<T, sub>(f, std::vector<int>(internal::log(d, f.size()), d)); } } // namespace suisen::kronecker_transform