多项式多点求值
cpp
// 多项式多点求值
vector<int> evals(const poly &f,vector<int> &x){
vector<poly> T;
int n=f.size(),m=x.size();
T.assign(m<<2,{});
function<void(int,int,int)> build=[&](int p,int l,int r){
if(l==r){
T[p]={(P-x[l])%P,1};
return;
}
int mid=l+r>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r);
T[p]=mul(T[p<<1],T[p<<1|1]);
while(T[p].size()>1&&T[p].back()==0)T[p].pop_back();
};
vector<int> res(m);
function<void(int,int,int,poly)> solve=[&](int p,int l,int r,poly f){
if(r-l+1<=64){
for(int i=l;i<=r;i++){
res[i]=eval(f,x[i]);
}
return;
}
auto [q1,r1]=div(f,T[p<<1]);
auto [q2,r2]=div(f,T[p<<1|1]);
while(r1.size()>1&&r1.back()==0)r1.pop_back();
while(r2.size()>1&&r2.back()==0)r2.pop_back();
int mid=l+r>>1;
solve(p<<1,l,mid,r1);
solve(p<<1|1,mid+1,r,r2);
};
build(1,0,m-1);
if(f.size()>=T[1].size()){
auto [q,r]=div(f,T[1]);
solve(1,0,m-1,r);
}
else solve(1,0,m-1,f);
return res;
}
void solve(){
int n,m;
cin>>n>>m;
n++;
vector<int> f(n),a(m);
for(int i=0;i<n;i++)cin>>f[i];
for(int i=0;i<m;i++)cin>>a[i];
auto ans=evals(f,a);
for(int i=0;i<m;i++)cout<<ans[i]<<"\n";
}