cp-library-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub NotLeonian/cp-library-cpp

:warning: Kronecker
(library/transform/kronecker.hpp)

Kronecker

Depends on

Code

#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 RandomAccessibleContainer>
    struct StepView {
        using iterator   = typename RandomAccessibleContainer::iterator;
        using value_type = typename RandomAccessibleContainer::value_type;
        using reference  = typename RandomAccessibleContainer::reference;
        
        StepView(RandomAccessibleContainer& 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
Back to top page