test/src/convolution/polynomial_eval/nim_counting.test.cpp

• View this file on GitHub
• Last update: 2023-09-15 20:02:25+09:00
• Problem: https://atcoder.jp/contests/abc212/tasks/abc212_h

Depends on

• 列を変数として持つ多項式の評価 (library/convolution/polynomial_eval.hpp)
• クロネッカー冪による線形変換 (仮称) (library/transform/kronecker_power.hpp)
• Walsh Hadamard 変換 (library/transform/walsh_hadamard.hpp)
• Type Traits (library/type_traits/type_traits.hpp)
• Default Operator (library/util/default_operator.hpp)

Code

#define PROBLEM "https://atcoder.jp/contests/abc212/tasks/abc212_h"

#include <iostream>
#include <atcoder/modint>

#include "library/transform/walsh_hadamard.hpp"
#include "library/convolution/polynomial_eval.hpp"
using namespace suisen;

using mint = atcoder::modint998244353;

constexpr int M = 1 << 16;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, k;
    std::cin >> n >> k;

    std::vector<mint> c(M, 0);
    for (int i = 0; i < k; ++i) {
        int v;
        std::cin >> v;
        ++c[v];
    }

    using namespace walsh_hadamard_transform;

    auto res = suisen::polynomial_eval<mint, walsh_hadamard<mint>, walsh_hadamard_inv<mint>>(c, [n](mint x) {
        return x == 1 ? n : x * (x.pow(n) - 1) / (x - 1);
        });

    std::cout << std::accumulate(res.begin() + 1, res.end(), mint(0)).val() << std::endl;

    return 0;
}

#line 1 "test/src/convolution/polynomial_eval/nim_counting.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc212/tasks/abc212_h"

#include <iostream>
#include <atcoder/modint>

#line 1 "library/transform/walsh_hadamard.hpp"



#line 1 "library/transform/kronecker_power.hpp"



#include <cassert>
#include <utility>
#include <vector>

#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 9 "library/transform/kronecker_power.hpp"

namespace suisen {
    namespace kronecker_power_transform {
        namespace internal {
            template <typename UnitTransform, typename ReferenceGetter, std::size_t... Seq>
            void unit_transform(UnitTransform transform, ReferenceGetter ref_getter, std::index_sequence<Seq...>) {
                transform(ref_getter(Seq)...);
            }
        }

        template <typename T, std::size_t D, auto unit_transform>
        void kronecker_power_transform(std::vector<T> &x) {
            const std::size_t n = x.size();
            for (std::size_t block = 1; block < n; block *= D) {
                for (std::size_t l = 0; l < n; l += D * block) {
                    for (std::size_t offset = l; offset < l + block; ++offset) {
                        const auto ref_getter = [&](std::size_t i) -> T& { return x[offset + i * block]; };
                        internal::unit_transform(unit_transform, ref_getter, std::make_index_sequence<D>());
                    }
                }
            }
        }

        template <typename T, typename UnitTransform>
        void kronecker_power_transform(std::vector<T> &x, const std::size_t D, UnitTransform unit_transform) {
            const std::size_t n = x.size();
            std::vector<T> work(D);
            for (std::size_t block = 1; block < n; block *= D) {
                for (std::size_t l = 0; l < n; l += D * block) {
                    for (std::size_t offset = l; offset < l + block; ++offset) {
                        for (std::size_t i = 0; i < D; ++i) work[i] = x[offset + i * block];
                        unit_transform(work);
                        for (std::size_t i = 0; i < D; ++i) x[offset + i * block] = work[i];
                    }
                }
            }
        }

        template <typename T, auto e = default_operator::zero<T>, auto add = default_operator::add<T>, auto mul = default_operator::mul<T>>
        auto kronecker_power_transform(std::vector<T> &x, const std::vector<std::vector<T>> &A) -> decltype(e(), add(std::declval<T>(), std::declval<T>()), mul(std::declval<T>(), std::declval<T>()), void()) {
            const std::size_t D = A.size();
            assert(D == A[0].size());
            auto unit_transform = [&](std::vector<T> &x) {
                std::vector<T> y(D, e());
                for (std::size_t i = 0; i < D; ++i) for (std::size_t j = 0; j < D; ++j) {
                    y[i] = add(y[i], mul(A[i][j], x[j]));
                }
                x.swap(y);
            };
            kronecker_power_transform<T>(x, D, unit_transform);
        }
    }
} // namespace suisen



#line 5 "library/transform/walsh_hadamard.hpp"

namespace suisen::walsh_hadamard_transform {
    namespace internal {
        template <typename T, auto add = default_operator::add<T>, auto sub = default_operator::sub<T>>
        void unit_transform(T& x0, T& x1) {
            T y0 = x0, y1 = x1;
            x0 = add(y0, y1);   // 1,  1
            x1 = sub(y0, y1);   // 1, -1
        }
    } // namespace internal

    using kronecker_power_transform::kronecker_power_transform;

    template <typename T, auto add = default_operator::add<T>, auto sub = default_operator::sub<T>>
    void walsh_hadamard(std::vector<T>& a) {
        kronecker_power_transform<T, 2, internal::unit_transform<T, add, sub>>(a);
    }
    template <typename T, auto add = default_operator::add<T>, auto sub = default_operator::sub<T>, auto div = default_operator::div<T>, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr>
    void walsh_hadamard_inv(std::vector<T>& a) {
        walsh_hadamard<T, add, sub>(a);
        const T n{ a.size() };
        for (auto& val : a) val = div(val, n);
    }
    template <typename T, auto add = default_operator::add<T>, auto sub = default_operator::sub<T>, auto mul = default_operator::mul<T>, auto inv = default_operator::inv<T>, std::enable_if_t<std::negation_v<std::is_integral<T>>, std::nullptr_t> = nullptr>
    void walsh_hadamard_inv(std::vector<T>& a) {
        walsh_hadamard<T, add, sub>(a);
        const T n{ a.size() };
        const T inv_n = inv(n);
        for (auto& val : a) val = mul(val, inv_n);
    }
} // namespace suisen::walsh_hadamard_transform



#line 1 "library/convolution/polynomial_eval.hpp"



#line 5 "library/convolution/polynomial_eval.hpp"

#line 1 "library/type_traits/type_traits.hpp"



#include <limits>
#line 6 "library/type_traits/type_traits.hpp"
#include <type_traits>

namespace suisen {
    template <typename ...Constraints> using constraints_t = std::enable_if_t<std::conjunction_v<Constraints...>, std::nullptr_t>;

    template <typename T, typename = std::nullptr_t> struct bitnum { static constexpr int value = 0; };
    template <typename T> struct bitnum<T, constraints_t<std::is_integral<T>>> { static constexpr int value = std::numeric_limits<std::make_unsigned_t<T>>::digits; };
    template <typename T> static constexpr int bitnum_v = bitnum<T>::value;
    template <typename T, size_t n> struct is_nbit { static constexpr bool value = bitnum_v<T> == n; };
    template <typename T, size_t n> static constexpr bool is_nbit_v = is_nbit<T, n>::value;

    template <typename T, typename = std::nullptr_t> struct safely_multipliable { using type = T; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 32>>> { using type = long long; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 64>>> { using type = __int128_t; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 32>>> { using type = unsigned long long; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 64>>> { using type = __uint128_t; };
    template <typename T> using safely_multipliable_t = typename safely_multipliable<T>::type;

    template <typename T, typename = void> struct rec_value_type { using type = T; };
    template <typename T> struct rec_value_type<T, std::void_t<typename T::value_type>> {
        using type = typename rec_value_type<typename T::value_type>::type;
    };
    template <typename T> using rec_value_type_t = typename rec_value_type<T>::type;

    template <typename T> class is_iterable {
        template <typename T_> static auto test(T_ e) -> decltype(e.begin(), e.end(), std::true_type{});
        static std::false_type test(...);
    public:
        static constexpr bool value = decltype(test(std::declval<T>()))::value;
    };
    template <typename T> static constexpr bool is_iterable_v = is_iterable<T>::value;
    template <typename T> class is_writable {
        template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::ostream&>() << e, std::true_type{});
        static std::false_type test(...);
    public:
        static constexpr bool value = decltype(test(std::declval<T>()))::value;
    };
    template <typename T> static constexpr bool is_writable_v = is_writable<T>::value;
    template <typename T> class is_readable {
        template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::istream&>() >> e, std::true_type{});
        static std::false_type test(...);
    public:
        static constexpr bool value = decltype(test(std::declval<T>()))::value;
    };
    template <typename T> static constexpr bool is_readable_v = is_readable<T>::value;
} // namespace suisen

#line 7 "library/convolution/polynomial_eval.hpp"

namespace suisen {
    template <typename T, auto transform, auto transform_inv, typename F, constraints_t<std::is_invocable_r<T, F, T>> = nullptr>
    std::vector<T> polynomial_eval(std::vector<T> &&a, F f) {
        transform(a);
        for (auto &x : a) x = f(x);
        transform_inv(a);
        return a;
    }

    template <typename T, auto transform, auto transform_inv, typename F, constraints_t<std::is_invocable_r<T, F, T>> = nullptr>
    std::vector<T> polynomial_eval(const std::vector<T> &a, F f) {
        return polynomial_eval<T, transform, transform_inv>(std::vector<T>(a), f);
    }
} // namespace suisen


#line 8 "test/src/convolution/polynomial_eval/nim_counting.test.cpp"
using namespace suisen;

using mint = atcoder::modint998244353;

constexpr int M = 1 << 16;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, k;
    std::cin >> n >> k;

    std::vector<mint> c(M, 0);
    for (int i = 0; i < k; ++i) {
        int v;
        std::cin >> v;
        ++c[v];
    }

    using namespace walsh_hadamard_transform;

    auto res = suisen::polynomial_eval<mint, walsh_hadamard<mint>, walsh_hadamard_inv<mint>>(c, [n](mint x) {
        return x == 1 ? n : x * (x.pow(n) - 1) / (x - 1);
        });

    std::cout << std::accumulate(res.begin() + 1, res.end(), mint(0)).val() << std::endl;

    return 0;
}

Back to top page