列を変数として持つ多項式の評価
(library/convolution/polynomial_eval.hpp)

• View this file on GitHub
• Last update: 2023-09-15 20:02:25+09:00
• Include: #include "library/convolution/polynomial_eval.hpp"

polynomial_eval

• シグネチャ

  template <typename T, auto transform, auto transform_inv, typename F>
  std::vector<T> polynomial_eval(std::vector<T> &&a, F f) // (1)
  
  template <typename T, auto transform, auto transform_inv, typename F>
  std::vector<T> polynomial_eval(const std::vector<T> &a, F f) // (2)
  

• 概要

  列 $A$ を変数に持つ多項式 $\displaystyle f(A)=\sum_{i=0}^{M-1} C_i \cdot A^i$ を評価します．ここで，$A^i$ はある畳み込み演算 $\ast$ に対して以下で定義されるものとします．

  \[A^i = \underbrace{A \ast A \ast \cdots \ast A}_{i}\]

  また，$\ast$ に対してある正則な変換行列 $\mathcal{F}$ が存在して，任意の列 $X,Y$ に対して

  \[\mathcal{F}[X] \odot \mathcal{F}[Y]=\mathcal{F}[X\ast Y]\]

  を満たす必要があります．ここで，$\odot$ は各点積をとる演算です．このとき，$f(A)$ は次のように計算されます．

  \[\begin{aligned} f(A) &=\mathcal{F}^{-1}\left[\sum_{i=0}^{M-1}C_i\cdot \left(\underbrace{\mathcal{F}[A]\odot\cdots\odot\mathcal{F}[A]}_{i}\right)\right]\\ &=\mathcal{F}^{-1}\left[\begin{pmatrix} f(\mathcal{F}[A]_0)\\ f(\mathcal{F}[A]_1)\\ \vdots\\ f(\mathcal{F}[A]_{\vert A\vert-1})\\ \end{pmatrix}\right] \end{aligned}\]

  上式における $\mathcal{F}$ と $\mathcal{F}^{-1}$ による変換を与えるのがテンプレート引数 transform および transform_inv であり，$f(\cdot)$ を評価するのが引数 f です．

• テンプレート引数

  • T: 列の要素の型．
  • transform: 列に対して inplace に線形変換 $\mathcal{F}$ を施す関数
  • transform_inv: 逆変換 $\mathcal{F}^{-1}$ を施す関数
  • F: T 型の要素 $x$ に対して $\displaystyle f(x)=\sum_{i=0}^{N-1}C_i \cdot x^i$ を計算する関数の型です．F 型のインスタンス f は x を引数に取る関数呼び出し f(x) によって $f(x)$ を計算できなければなりません．

• 引数

  • a: 列 $A$
  • f: $f(x)$ を評価する関数

• 返り値

  $f(A)$

• 時間計算量

  列 $A$ の長さを $N$，transform の計算量を $\Theta(f(N))$, transform_inv の計算量を $\Theta(g(N))$，f の計算量を $O(h(M))$ として，$\Theta(f(N)+g(N)+N\cdot h(M))$ です．

Depends on

• Type Traits (library/type_traits/type_traits.hpp)

Verified with

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

Code

#ifndef SUISEN_APPLY_POLYNOMIAL
#define SUISEN_APPLY_POLYNOMIAL

#include <vector>

#include "library/type_traits/type_traits.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

#endif // SUISEN_APPLY_POLYNOMIAL

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



#include <vector>

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



#include <limits>
#include <iostream>
#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

Back to top page