multipoint evaluation
(include/emthrm/math/formal_power_series/multipoint_evaluation.hpp)
複数の $x$ に対して $f(x)$ を求めるアルゴリズムである。
時間計算量
$\langle O(N(\log{N})^2), O(N(\log{N})^2) \rangle$
仕様
template < template < typename > class C , typename T >
struct MultipointEvaluation ;
メンバ変数
名前
説明
std::vector<T> f_x
$\lbrace f(x) \mid x \in \mathrm{xs} \rbrace$
std::vector<C<T>> subproduct_tree
subproduct tree
メンバ関数
名前
効果
explicit MultipointEvaluation(const std::vector<T> &xs);
multipoint evaluation を考える。
void build(const C<T>& f);
多項式 $f$ に対して f_x
を構築する。
参考文献
Allan Borodin and Robert Moen: Fast modular transforms, Journal of Computer and System Sciences , Vol. 8, No. 3, pp. 366–386 (1974). https://doi.org/10.1016/S0022-0000(74)80029-2
https://www.sci.kanagawa-u.ac.jp/info/matsuo/pub/pdf/IKM09.pdf
https://judge.yosupo.jp/submission/3271
https://scrapbox.io/ecasdqina-cp/%E5%A4%9A%E9%A0%85%E5%BC%8F%E3%82%92%E3%83%9E%E3%83%BC%E3%82%B8%E3%81%99%E3%82%8B%E4%B8%80%E8%88%AC%E7%9A%84%EF%BC%88%EF%BC%9F%EF%BC%89%E3%81%AA%E3%83%86%E3%82%AF
TODO
https://drive.google.com/drive/folders/1gszRctvUfme7ST-K3DsrH7FIU64kHcsD
Submissons
https://judge.yosupo.jp/submission/3793
Required by
Verified with
Code
#ifndef EMTHRM_MATH_FORMAL_POWER_SERIES_MULTIPOINT_EVALUATION_HPP_
#define EMTHRM_MATH_FORMAL_POWER_SERIES_MULTIPOINT_EVALUATION_HPP_
#include <algorithm>
#include <iterator>
#include <vector>
namespace emthrm {
template < template < typename > class C , typename T >
struct MultipointEvaluation {
std :: vector < T > f_x ;
std :: vector < C < T >> subproduct_tree ;
explicit MultipointEvaluation ( const std :: vector < T > & xs )
: f_x ( xs . size ()), subproduct_tree ( xs . size () << 1 ), n ( xs . size ()) {
std :: transform ( xs . begin (), xs . end (), std :: next ( subproduct_tree . begin (), n ),
[]( const T & x ) -> C < T > { return C < T > { - x , 1 }; });
for ( int i = n - 1 ; i > 0 ; -- i ) {
subproduct_tree [ i ] =
subproduct_tree [ i << 1 ] * subproduct_tree [( i << 1 ) + 1 ];
}
}
void build ( const C < T >& f ) { dfs ( f , 1 ); }
private:
const int n ;
void dfs ( C < T > f , int node ) {
f %= subproduct_tree [ node ];
if ( node < n ) {
dfs ( f , node << 1 );
dfs ( f , ( node << 1 ) + 1 );
} else {
f_x [ node - n ] = f [ 0 ];
}
}
};
} // namespace emthrm
#endif // EMTHRM_MATH_FORMAL_POWER_SERIES_MULTIPOINT_EVALUATION_HPP_
#line 1 "include/emthrm/math/formal_power_series/multipoint_evaluation.hpp"
#include <algorithm>
#include <iterator>
#include <vector>
namespace emthrm {
template < template < typename > class C , typename T >
struct MultipointEvaluation {
std :: vector < T > f_x ;
std :: vector < C < T >> subproduct_tree ;
explicit MultipointEvaluation ( const std :: vector < T > & xs )
: f_x ( xs . size ()), subproduct_tree ( xs . size () << 1 ), n ( xs . size ()) {
std :: transform ( xs . begin (), xs . end (), std :: next ( subproduct_tree . begin (), n ),
[]( const T & x ) -> C < T > { return C < T > { - x , 1 }; });
for ( int i = n - 1 ; i > 0 ; -- i ) {
subproduct_tree [ i ] =
subproduct_tree [ i << 1 ] * subproduct_tree [( i << 1 ) + 1 ];
}
}
void build ( const C < T >& f ) { dfs ( f , 1 ); }
private:
const int n ;
void dfs ( C < T > f , int node ) {
f %= subproduct_tree [ node ];
if ( node < n ) {
dfs ( f , node << 1 );
dfs ( f , ( node << 1 ) + 1 );
} else {
f_x [ node - n ] = f [ 0 ];
}
}
};
} // namespace emthrm
Back to top page