Kyopro Library
 
読み取り中…
検索中…
一致する文字列を見つけられません
multipoint_evaluate.hpp
[詳解]
1#pragma once
2#include"../../kyopro_library/template.hpp"
3#include"../../kyopro_library/math/fps.hpp"
4
5/// @brief n 次多項式 f について、n 個の点 x[i] における f(x[i]) を返す
6/// @note O(n (log(n))^2)
7template<typename T>
8vector<T> MultipointEvaluate(vector<T> f, vector<T> x) {
9 int n=x.size();
10 if(n==0) return{};
11 if(n==1) {
12 T ret=0,tmp=1;
13 for(T a:f) ret+=a*tmp,tmp*=x[0];
14 return {ret};
15 }
16 int n2=1;
17 while(n2<n) n2<<=1;
18 vector<vector<T>> g(n2*2,{1});
19 for(int i=0; i<n; i++) g[n2+i]={-x[i],1};
20 for(ll i=n2-1; i>0; i--) g[i]=PolyMul(g[i<<1],g[i<<1|1]);
21
22 g[1]=PolyDiv(f,g[1]).second;
23 for(int i=2; i<n2+n; i++) g[i]=PolyDiv(g[i>>1],g[i]).second;
24 vector<T> ret(n);
25 for(int i=0; i<n; i++) ret[i]=g[n2+i][0];
26 return ret;
27}
vector< T > MultipointEvaluate(vector< T > f, vector< T > x)
n 次多項式 f について、n 個の点 x[i] における f(x[i]) を返す