kyopro library

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

View the Project on GitHub Chipppppppppp/kyopro

:warning: kpr/algorithm/algorithm.hpp

Depends on

Required by

Code

#pragma once
#include "bit.hpp"
#include "compress.hpp"
#include "contains.hpp"
#include "count_all.hpp"
#include "Hash.hpp"
#include "next_combination.hpp"
#line 2 "kpr/algorithm/bit.hpp"
#include <limits>
#include <type_traits>
#line 2 "kpr/meta/setting.hpp"
#include <cstdint>

#ifndef KYOPRO_BASE_INT
// 基本符号付き整数型

#define KYOPRO_BASE_INT std::int64_t
#endif

#ifndef KYOPRO_BASE_UINT
// 基本符号なし整数型

#define KYOPRO_BASE_UINT std::uint64_t
#endif

#ifndef KYOPRO_BASE_FLOAT
// 基本浮動小数点数型

#define KYOPRO_BASE_FLOAT double
#endif

#ifndef KYOPRO_LL
// ll

#define KYOPRO_LL long long
#endif

#ifndef KYOPRO_LF
// lf

#define KYOPRO_LF double
#endif

#ifndef KYOPRO_MINT
// mint

#define KYOPRO_MINT kpr::ModInt<mod>
#endif

#ifndef KYOPRO_DEFAULT_MOD
// 問題で設定されたmod

#define KYOPRO_DEFAULT_MOD (static_cast<KYOPRO_BASE_UINT>(998244353))
#endif

#ifndef KYOPRO_DECIMAL_PRECISION
// 小数精度(桁)

#define KYOPRO_DECIMAL_PRECISION (static_cast<KYOPRO_BASE_UINT>(12))
#endif

#ifndef KYOPRO_INF_DIV
// 無限大を表す整数が最大値の何分の一かを表す

#define KYOPRO_INF_DIV (static_cast<KYOPRO_BASE_UINT>(3))
#endif

#ifndef KYOPRO_BUFFER_SIZE
// デフォルトのバッファサイズ

#define KYOPRO_BUFFER_SIZE (static_cast<KYOPRO_BASE_UINT>(2048))
#endif

#ifndef KYOPRO_BINOM_MOD_MAX
// デフォルトのBinomModの計算上限

#define KYOPRO_BINOM_MOD_MAX (static_cast<KYOPRO_BASE_UINT>(1000000))
#endif
#line 2 "kpr/meta/trait.hpp"
#include <cstddef>
#include <iterator>
#include <tuple>
#line 6 "kpr/meta/trait.hpp"
#include <utility>

namespace kpr {
    namespace helper {
        template<class T>
        struct is_integer_helper {
            static constexpr bool value = std::is_integral_v<T>;
        };

        #ifdef __SIZEOF_INT128__
        template<>
        struct is_integer_helper<__int128_t> {
            static constexpr bool value = true;
        };
        template<>
        struct is_integer_helper<__uint128_t> {
            static constexpr bool value = true;
        };
        #endif
    } // namespace helper


    // 型Tが整数か調べる

    template<class T>
    struct is_integer {
        static constexpr bool value = helper::is_integer_helper<std::remove_cv_t<T>>::value;
    };
    // 型Tが整数か調べる

    template<class T>
    inline constexpr bool is_integer_v = is_integer<T>::value;

    // 型Tが符号付き整数か調べる

    template<class T>
    struct is_signed_integer {
        static constexpr bool value = is_integer_v<T> && std::is_signed_v<T>;
    };
    // 型Tが符号付き整数か調べる

    template<class T>
    inline constexpr bool is_signed_integer_v = is_signed_integer<T>::value;

    // 型Tが符号無し整数か調べる

    template<class T>
    struct is_unsigned_integer {
        static constexpr bool value = is_integer_v<T> && !std::is_signed_v<T>;
    };
    // 型Tが符号無し整数か調べる

    template<class T>
    inline constexpr bool is_unsigned_integer_v = is_unsigned_integer<T>::value;

    namespace helper {
        template<class T>
        struct is_floating_point_helper {
            static constexpr bool value = std::is_floating_point_v<T>;
        };

        #ifdef __SIZEOF_FLOAT128__
        template<>
        struct is_floating_point_helper<__float128> {
            static constexpr bool value = true;
        };
        #endif
    } // namespace helper


    // 型Tが浮動小数点数か調べる

    template<class T>
    struct is_floating_point {
        static constexpr bool value = helper::is_floating_point_helper<std::remove_cv_t<T>>::value;
    };
    // 型Tが浮動小数点数か調べる

    template<class T>
    inline constexpr bool is_floating_point_v = is_floating_point<T>::value;

    // 型Tが算術型か調べる

    template<class T>
    struct is_arithmetic {
        static constexpr bool value = is_integer_v<T> || is_floating_point_v<T>;
    };
    // 型Tが算術型か調べる

    template<class T>
    inline constexpr bool is_arithmetic_v = is_arithmetic<T>::value;

    // 型Tがスカラーか調べる

    template<class T>
    struct is_scalar {
        static constexpr bool value = is_arithmetic_v<T> || std::is_enum_v<T> || std::is_pointer_v<T> || std::is_member_pointer_v<T> || std::is_null_pointer_v<T>;
    };
    // 型Tがスカラーか調べる

    template<class T>
    inline constexpr bool is_scalar_v = is_scalar<T>::value;

    // size以上の大きさを持つ最小の符号付き整数を調べる

    template<std::size_t size>
    struct int_least {
    private:
        static constexpr auto get_type() noexcept {
            static_assert(size <= 128, "The given integer type is too large");
            if constexpr (size <= 8) return std::int_least8_t{};
            else if constexpr (size <= 16) return std::int_least16_t{};
            else if constexpr (size <= 32) return std::int_least32_t{};
            else if constexpr (size <= 64) return std::int_least64_t{};
            else return __int128_t{};
        }

    public:
        using type = decltype(get_type());
    };
    // size以上の大きさを持つ最小の符号付き整数を調べる

    template<std::size_t size>
    using int_least_t = typename int_least<size>::type;

    // size以上の大きさを持つ最小の符号無し整数を調べる

    template<std::size_t size>
    struct uint_least {
    private:
        static constexpr auto get_type() noexcept {
            static_assert(size <= 128, "The give integer type is too large");
            if constexpr (size <= 8) return std::uint_least8_t{};
            else if constexpr (size <= 16) return std::uint_least16_t{};
            else if constexpr (size <= 32) return std::uint_least32_t{};
            else if constexpr (size <= 64) return std::uint_least64_t{};
            else return __uint128_t{};
        }

    public:
        using type = decltype(get_type());
    };
    // size以上の大きさを持つ最小の符号無し整数を調べる

    template<std::size_t size>
    using uint_least_t = typename uint_least<size>::type;

    // Tの次に大きい整数型を調べる

    template<class T>
    struct next_integer {
        static_assert(is_integer_v<T>, "The given type must be an integer type");
        static_assert(sizeof(T) <= 8, "The given integer type is too large");
        using type = std::conditional_t<std::is_signed_v<T>, int_least_t<sizeof(T) * 16>, uint_least_t<sizeof(T) * 16>>;
    };
    // Tの次に大きい整数型を調べる

    template<class T>
    using next_integer_t = typename next_integer<T>::type;

    // Tの次に小さい整数型を調べる

    template<class T>
    struct prev_integer {
        static_assert(is_integer_v<T>, "The given type must be an integer type");
        static_assert(sizeof(T) >= 2, "The given integer type is too large");
        using type = std::conditional_t<std::is_signed_v<T>, int_least_t<sizeof(T) * 4>, uint_least_t<sizeof(T) * 4>>;
    };
    // Tの次に小さい整数型を調べる

    template<class T>
    using prev_integer_t = typename prev_integer<T>::type;

    // 型Tがイテレータか調べる

    template<class T, class = void>
    struct is_iterator {
        static constexpr bool value = false;
    };
    template<class T>
    struct is_iterator<T, std::void_t<typename std::iterator_traits<T>::iterator_category>> {
        static constexpr bool value = true;
    };
    // 型Tがイテレータか調べる

    template<class T>
    inline constexpr bool is_iterator_v = is_iterator<T>::value;

    // 型TがRangeか調べる

    template<class T, class = void>
    struct is_range {
        static constexpr bool value = false;
    };
    template<class T>
    struct is_range<T, std::void_t<decltype(std::begin(std::declval<std::add_lvalue_reference_t<T>>()), std::end(std::declval<std::add_lvalue_reference_t<T>>()))>> {
        static constexpr bool value = true;
    };
     // 型TがRangeか調べる

    template<class T>
    inline constexpr bool is_range_v = is_range<T>::value;

    // Range型Tからイテレータの型を調べる

    template<class T>
    struct range_iterator {
        using type = std::decay_t<decltype(std::begin(std::declval<T>()))>;
    };
    // Range型Tからイテレータの型を調べる

    template<class T>
    using range_iterator_t = typename range_iterator<T>::type;

    // Range型Tから読み取り専用イテレータの型を調べる

    template<class T>
    struct range_const_iterator {
        using type = std::decay_t<decltype(std::cbegin(std::declval<T>()))>;
    };
    // Range型Tから読み取り専用イテレータの型を調べる

    template<class T>
    using range_const_iterator_t = typename range_iterator<T>::type;

    // Range型Tから要素の型を調べる

    template<class T>
    struct range_value {
        using type = std::decay_t<decltype(*std::begin(std::declval<T>()))>;
    };
    // Range型Tから要素の型を調べる

    template<class T>
    using range_value_t = typename range_value<T>::type;
} // namespace kpr

#line 6 "kpr/algorithm/bit.hpp"

namespace kpr {
    // 立っているbitの個数を返す

    [[maybe_unused]] inline constexpr struct {
        template<class T>
        constexpr KYOPRO_BASE_INT operator ()(T x) const noexcept {
            static_assert(is_integer_v<T>, "The argument must be an integer");
            constexpr auto digits = std::numeric_limits<std::make_unsigned_t<T>>::digits;
            static_assert(digits <= std::numeric_limits<unsigned long long>::digits, "The integer type of the argument is too large");
            if constexpr (digits <= std::numeric_limits<unsigned int>::digits) return __builtin_popcount(x);
            else if constexpr (digits <= std::numeric_limits<unsigned long>::digits) return __builtin_popcountl(x);
            else return __builtin_popcountll(x);
        }
    } pop_count;

    // 最上位bitより左の連続した0ビットの数を返す

    [[maybe_unused]] inline constexpr struct {
        template<class T>
        constexpr KYOPRO_BASE_INT operator ()(T x) const noexcept {
            static_assert(is_integer_v<T>, "The argument must be an integer");
            constexpr auto digits = std::numeric_limits<std::make_unsigned_t<T>>::digits;
            static_assert(digits <= std::numeric_limits<unsigned long long>::digits, "The integer type of the argument is too large");
            if (x == 0) return 0;
            if constexpr (digits <= std::numeric_limits<unsigned int>::digits) return __builtin_clz(x) + digits - std::numeric_limits<unsigned int>::digits;
            else if constexpr (digits <= std::numeric_limits<unsigned long>::digits) return __builtin_clzl(x) + digits - std::numeric_limits<unsigned long>::digits;
            else return __builtin_clzll(x) + digits - std::numeric_limits<unsigned long long>::digits;
        }
    } lzero_count;

    // 1の位から連続した0ビットの数を返す

    [[maybe_unused]] inline constexpr struct {
        template<class T>
        constexpr KYOPRO_BASE_INT operator ()(T x) const noexcept {
            static_assert(is_integer_v<T>, "The argument must be an integer");
            constexpr auto digits = std::numeric_limits<std::make_unsigned_t<T>>::digits;
            if (x == 0) return digits;
            static_assert(digits <= std::numeric_limits<unsigned long long>::digits, "The integer type of the argument is too large");
            if constexpr (digits <= std::numeric_limits<unsigned int>::digits) return __builtin_ctz(x);
            else if constexpr (digits <= std::numeric_limits<unsigned long>::digits) return __builtin_ctzl(x);
            else return __builtin_ctzll(x);
        }
    } rzero_count;

    // ビット幅を返す

    [[maybe_unused]] inline constexpr struct {
        template<class T>
        constexpr KYOPRO_BASE_INT operator ()(T x) const noexcept {
            static_assert(is_integer_v<T>, "The argument must be an integer");
            constexpr auto digits = std::numeric_limits<std::make_unsigned_t<T>>::digits;
            static_assert(digits <= std::numeric_limits<unsigned long long>::digits, "The integer type of the argument is too large");
            if (x == 0) return 0;
            if constexpr (digits <= std::numeric_limits<unsigned int>::digits) return std::numeric_limits<unsigned int>::digits - __builtin_clz(x);
            else if constexpr (digits <= std::numeric_limits<unsigned long>::digits) return std::numeric_limits<unsigned long>::digits - __builtin_clzl(x);
            else return std::numeric_limits<unsigned long long>::digits - __builtin_clzll(x);
        }
    } bit_len;

    // 1 << n が与えられた数以下である最大の n を返す (0 の場合、0を返す)

    [[maybe_unused]] inline constexpr struct {
        template<class T>
        constexpr KYOPRO_BASE_INT operator ()(T x) const noexcept {
            return bit_len(x >> static_cast<T>(1));
        }
    } floor_bit;

    // 1 << n が与えられた数以上である最小の n を返す

    [[maybe_unused]] inline constexpr struct {
        template<class T>
        constexpr KYOPRO_BASE_INT operator ()(T x) const noexcept {
            if (x == 0) return 0;
            return bit_len(x - static_cast<T>(1));
        }
    } ceil_bit;
} // namespace kpr

#line 2 "kpr/algorithm/compress.hpp"
#include <algorithm>
#line 4 "kpr/algorithm/compress.hpp"
#include <unordered_map>
#include <vector>
#line 2 "kpr/function/compare.hpp"

namespace kpr {
    // operator =で比較

    struct Equal {
        template<class T>
        constexpr bool operator()(const T& x, const T& y) const noexcept(noexcept(x == y)) {
            return x == y;
        }
    };

    // operator !=で比較

    struct NotEqual {
        template<class T>
        constexpr bool operator()(const T& x, const T& y) const noexcept(noexcept(x != y)) {
            return x != y;
        }
    };

    // operator <の関数クラス

    struct Less {
        template<class T>
        constexpr bool operator()(const T& x, const T& y) const noexcept(noexcept(x < y)) {
            return x < y;
        }
    };

    // operator <=の関数クラス

    struct LessEqual {
        template<class T>
        constexpr bool operator()(const T& x, const T& y) const noexcept(noexcept(x <= y)) {
            return x <= y;
        }
    };

    // operator >の関数クラス

    struct Greater {
        template<class T>
        constexpr bool operator()(const T& x, const T& y) const noexcept(noexcept(x > y)) {
            return x > y;
        }
    };

    // operator >=の関数クラス

    struct GreaterEqual {
        template<class T>
        constexpr bool operator()(const T& x, const T& y) const noexcept(noexcept(x >= y)) {
            return x >= y;
        }
    };
} // namespace kpr

#line 7 "kpr/algorithm/compress.hpp"

namespace kpr {
    // 座標圧縮
    [[maybe_unused]] inline constexpr struct {
        template<class T, class Compare = Less, class Container = std::unordered_map<typename std::iterator_traits<T>::value_type, KYOPRO_BASE_INT>>
        auto operator ()(T first, T last, Compare comp = {}) const {
            std::vector<typename Container::key_type> a(first, last);
            std::sort(a.begin(), a.end(), comp);
            auto itr = unique(a.begin(), a.end());
            Container mem;
            int cnt = -1;
            for (auto i = std::begin(a); i != itr; ++i) mem[*i] = ++cnt;
            return mem;
        }
    } compress;
} // namespace kpr
#line 6 "kpr/meta/tuple_like.hpp"

namespace kpr {
    namespace helper {
        struct CastableToAny {
            template<class T>
            operator T() const noexcept;
        };

        template<class T, std::size_t... idx, std::void_t<decltype(T{((void)idx, CastableToAny{})...})>* = nullptr>
        constexpr bool is_constructible_with(std::index_sequence<idx...>, bool) noexcept {
            return true;
        }
        template<class T, std::size_t... idx>
        constexpr bool is_constructible_with(std::index_sequence<idx...>, char) noexcept {
            return false;
        }

        template<class T, std::size_t n = sizeof(T) * 8, class = void>
        struct constructible_size {
            static_assert(n != 0, "T is not constructible");
            static constexpr std::size_t value = constructible_size<T, n - 1>::value;
        };

        template<class T, std::size_t n>
        struct constructible_size<T, n, std::enable_if_t<is_constructible_with<T>(std::make_index_sequence<n>(), false)>> {
            static constexpr std::size_t value = n;
        };
    } // namespace helper


    // tuple_likeな型Tの大きさを調べる
    template<class T, class = void>
    struct tuple_like_size {
        static constexpr std::size_t value = helper::constructible_size<T>::value;
    };

    template<class T>
    struct tuple_like_size<T, std::void_t<decltype(std::tuple_size<T>::value)>> {
        static constexpr std::size_t value = std::tuple_size_v<T>;
    };

    // tuple_likeな型Tの大きさを調べる
    template<class T>
    inline constexpr std::size_t tuple_like_size_v = tuple_like_size<T>::value;


    // tuple_likeなオブジェクトのidx(0 <= idx < 8)番目を求める関数クラス
    template<class T, class = void>
    struct GetFunction {
        #define GET(...) \
            { \
                auto&& [__VA_ARGS__] = std::forward<U>(tuple_like); \
                return std::get<idx> (std::forward_as_tuple(__VA_ARGS__)); \
            }

        template<std::size_t idx, class U>
        static constexpr decltype(auto) get(U&& tuple_like) noexcept {
            constexpr std::size_t size = tuple_like_size_v<T>;
            static_assert(size != 0, "The size must not be 0");
            static_assert(size < 9, "The size of tuple_like must be less than 9");
            if constexpr (size == 1) GET(a)
            else if constexpr (size == 2) GET(a, b)
            else if constexpr (size == 3) GET(a, b, c)
            else if constexpr (size == 4) GET(a, b, c, d)
            else if constexpr (size == 5) GET(a, b, c, d, e)
            else if constexpr (size == 6) GET(a, b, c, d, e, f)
            else if constexpr (size == 7) GET(a, b, c, d, e, f, g)
            else GET(a, b, c, d, e, f, g, h)
        }

        #undef GET
    };

    template<class T>
    struct GetFunction<T, std::void_t<decltype(std::tuple_size<T>::value)>> {
        template<std::size_t idx, class U>
        static constexpr decltype(auto) get(U&& tuple_like) noexcept {
            return std::get<idx>(std::forward<U>(tuple_like));
        }
    };

    namespace helper {
        template<std::size_t idx>
        struct GetHelper {
            template<class T>
            constexpr decltype(auto) operator ()(T&& tuple_like) const noexcept {
                return GetFunction<std::decay_t<T>>::template get<idx>(std::forward<T>(tuple_like));
            }
        };
    }

    // tuple-likeなオブジェクトのidx(0 <= idx < 8)番目を求める
    template<std::size_t idx>
    inline constexpr helper::GetHelper<idx> get;


    // tuple-likeな型Tのidx(0 <= idx < 8)番目の要素の型を調べる
    template<std::size_t idx, class T>
    struct tuple_like_element {
        using type = std::decay_t<decltype(get<idx>(std::declval<T>()))>;
    };

    // tuple-likeな型Tのidx(0 <= idx < 8)番目の要素の型を調べる
    template<std::size_t idx, class T>
    using tuple_like_element_t = typename tuple_like_element<idx, T>::type;


    // 型Tがtuple_likeか調べる
    template<class T, class = void>
    struct is_tuple_like {
        static constexpr bool value = std::is_aggregate_v<T>;
    };

    template<class T>
    struct is_tuple_like<T, std::void_t<decltype(std::tuple_size<T>::value)>> {
        static constexpr bool value = true;
    };

    // 型Tがtuple_likeか調べる
    template<class T>
    inline constexpr bool is_tuple_like_v = is_tuple_like<T>::value;
} // namespace kpr
#line 6 "kpr/algorithm/contains.hpp"

namespace kpr {
    // 要素を含んでいるか調べる
    [[maybe_unused]] inline constexpr struct {
    private:
        template<class T>
        constexpr bool impl(const T& container, const typename T::key_type& value, char) const {
            return container.find(value) != container.end();
        }
        template<class T, std::enable_if_t<!is_tuple_like_v<T>>* = nullptr>
        constexpr bool impl(const T& container, const range_value_t<T>& value, bool) const {
            return std::find(std::begin(container), std::end(container), value) != std::end(container);
        }
        template<std::size_t i = 0, class T, class U, std::enable_if_t<is_tuple_like_v<T>>* = nullptr>
        constexpr bool impl(const T& tuple_like, const U& value, bool) const {
            if constexpr (i < tuple_like_size_v<T>) return get<i>(tuple_like) == value || impl<i + 1>(tuple_like, value, false);
            else return false;
        }

    public:
        template<class T, class U>
        constexpr bool operator ()(const T& a, const U& x) const {
            return impl(a, x, false);
        }
    } contains;
} // namespace kpr
#line 3 "kpr/algorithm/Hash.hpp"
#include <functional>
#line 9 "kpr/algorithm/Hash.hpp"

namespace kpr {
    // ハッシュ(tuple_like, range対応)

    template<class, class = void>
    struct Hash;

    template<class T>
    struct Hash<T, std::enable_if_t<std::is_scalar_v<T>>> {
        using value_type = T;

        constexpr std::size_t operator ()(T a) const noexcept {
            return std::hash<T>{}(a);
        }
    };

    template<class T>
    struct Hash<T, std::enable_if_t<is_tuple_like_v<T> && !is_range_v<T>>> {
        using value_type = T;

        template<std::size_t i = 0>
        constexpr std::size_t operator ()(const T& a) const noexcept {
            if constexpr (i == tuple_like_size_v<T>) return tuple_like_size_v<T>;
            else {
                std::size_t seed = operator()<i + 1>(a);
                return seed ^ (Hash<tuple_like_element_t<i, T>>{}(get<i>(a)) + 0x9e3779b97f4a7c15LU + (seed << 12) + (seed >> 4));
            }
        }
    };

    template<class T>
    struct Hash<T, std::enable_if_t<is_range_v<T>>>: Hash<range_value_t<T>> {
        using value_type = T;

        constexpr std::size_t operator ()(const T& a) const {
            std::size_t seed = std::size(a);
            for (auto&& i: a) seed ^= Hash<range_value_t<T>>{}(i) + 0x9e3779b97f4a7c15LU + (seed << 12) + (seed >> 4);
            return seed;
        }
    };
} // namespace kpr

#line 6 "kpr/algorithm/count_all.hpp"

namespace kpr {
    // 要素: 個数の辞書を返す
    [[maybe_unused]] inline constexpr struct {
        template<class T, class Container = std::unordered_map<typename std::iterator_traits<T>::value_type, KYOPRO_BASE_INT, Hash<typename std::iterator_traits<T>::value_type>>>
        auto operator ()(T first, T last) const {
            Container mem;
            for (auto i = first; i != last; ++i) ++mem[*i];
            return mem;
        }
    } count_all;
} // namespace kpr
#line 3 "kpr/algorithm/next_combination.hpp"

namespace kpr {
    // 先頭k個を次の組み合わせにして、次の組み合わせが存在するかを返す
    [[maybe_unused]] inline constexpr struct {
        template<class T>
        bool operator ()(T first, T last, int k) const {
            T subset = first + k;
            if (first == last || first == subset || last == subset) return false;
            T src = subset;
            while (first != src) {
                --src;
                if (*src < *(last - 1)) {
                    T dest = subset;
                    while (*src >= *dest) ++dest;
                    std::iter_swap(src, dest);
                    std::rotate(src + 1, dest + 1, last);
                    std::rotate(subset, subset + (last - dest) - 1, last);
                    return true;
                }
            }
            std::rotate(first, subset, last);
            return false;
        }
    } next_combination;
} // namespace kpr
#line 8 "kpr/algorithm/algorithm.hpp"
Back to top page