题解 P5050 【【模板】多项式多点求值】
AThousandSuns
2019-01-30 12:03:56
调了一个月终于调出来了……
这里就加点详细的注释表明哪里容易写错好了。毕竟没题解调这种题会死人的……
---
我们发现如果构造一个多项式 $P_{l,r}(x)=\prod\limits^r_{i=l}(x-a_i)$，那么对于所有的 $l\le i\le r$，都有 $P_{l,r}(a_i)=0$。
存在一个 $n-(r-l+1)$ 次多项式 $Q$，和 $r-l$ 次多项式 $R$ 满足 $F(a_i)=P_{l,r}(a_i)Q(a_i)+R(a_i)$。因为 $P_{l,r}(a_i)=0$，所以 $F(a_i)=R(a_i)$。我们便成功把一个 $n$ 次多项式变成了 $r-l$ 次多项式。
求 $R(a_i)$？发现它实际上是 $F$ 模 $P_{l,r}$，多项式除法/取模！
现在考虑分治。令 $F_{l,r}(x)$ 为当前区间的多项式，那么分成 $[l,mid]$ 和 $[mid+1,r]$ 计算。以 $[l,mid]$ 为例，$F_{l,r}(a_i)=P_{l,mid}(a_i)Q(a_i)+F_{l,mid}(a_i)$。
边界：$l=r$ 时 $F$ 次数为 $0$，那么 $F(a_i)=[x^0]F_{l,r}(x)$。
但是 $P_{l,r}(x)$ 直接求也不可承受。实际上我们可以另外再来一次分治，$P_{l,r}(x)=P_{l,mid}(x)P_{mid+1,r}(x)$。边界也是 $l=r$。
时间复杂度：$T(n)=2T(\frac{n}{2})+O(n\log n)=O(n\log^2n)$。
因为自带大常数，我就模仿了@officeyutong 的做法，在 $r-l\le100$ 的时候直接秦九韶爆算。实际上会跑得快很多。
下面是我的代码+注释：（我用vector写的，可能会比较丑）
```cpp
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,g=3;
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
inline int read(){
int x=0,f=0;char ch=getchar();
while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
int n,m,b[64444],ans[64444];
int limit,l,rev[266666];
vector<int> poly[266666],a;
inline void init(int upr){
for(limit=1,l=0;limit<=upr;limit<<=1,l++);
FOR(i,0,limit-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
}
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int sub(int x,int y){return x<y?x-y+mod:x-y;}
inline int qpow(int a,int b){
int ans=1;
for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) ans=1ll*ans*a%mod;
return ans;
}
void NTT(vector<int> &A,int tp){
while(A.size()<limit) A.push_back(0); //加上这话！不然会越界！
FOR(i,0,limit-1) if(i<rev[i]) swap(A[i],A[rev[i]]);
for(int i=1;i<limit;i<<=1)
for(int j=0,r=i<<1,Wn=qpow(g,mod-1+tp*(mod-1)/r);j<limit;j+=r)
for(int k=0,w=1;k<i;k++,w=1ll*w*Wn%mod){
int x=A[j+k],y=1ll*A[i+j+k]*w%mod;
A[j+k]=add(x,y);A[i+j+k]=sub(x,y);
}
if(tp==-1){
int linv=qpow(limit,mod-2);
FOR(i,0,limit-1) A[i]=1ll*A[i]*linv%mod;
}
}
void NTT(vector<int> A,vector<int> B,vector<int> &C){
C.clear(); //清空！
NTT(A,1);NTT(B,1);
FOR(i,0,limit-1) C.push_back(1ll*A[i]*B[i]%mod); //不能直接用下标！
NTT(C,-1);
}
void inv(vector<int> A,vector<int> &B,int deg){ //逆元（必须保证调用时B是空的）
if(deg==1) return B.push_back(qpow(A[0],mod-2));
inv(A,B,(deg+1)>>1);
init(deg<<1);
while(A.size()<limit) A.push_back(0); //虽然NTT内有补全到limit的话，但这也要写
FOR(i,deg,limit-1) A[i]=0; //因为这里需要把deg后的设为0
NTT(A,1);NTT(B,1);
FOR(i,0,limit-1) B[i]=1ll*sub(2,1ll*A[i]*B[i]%mod)*B[i]%mod;
NTT(B,-1);
FOR(i,deg,limit-1) B[i]=0;
}
void modulo(vector<int> A,vector<int> B,vector<int> &D,int n,int m){
//取模（须保证B高位为空，A随便）
while(A.size()<=n) A.push_back(0);
while(B.size()<=m) B.push_back(0); //把空位补全！（具体原因下文会说）
if(n<m) return void(D=A); //如果除不了，那么答案就是被除数！
vector<int> Arev,Brev,Brevinv,Crev,C;D.clear();
FOR(i,0,n) Arev.push_back(A[n-i]);
FOR(i,0,m) Brev.push_back(B[m-i]);
FOR(i,n-m+2,Arev.size()-1) Arev[i]=0;
FOR(i,n-m+1,Brev.size()-1) Brev[i]=0; //记得清零
inv(Brev,Brevinv,n-m+1);
init((n-m+1)<<1);
NTT(Arev,Brevinv,Crev);
FOR(i,0,n-m) C.push_back(Crev[n-m-i]);
init(n<<1);
NTT(B,C,D);
FOR(i,0,m-1) D[i]=sub(A[i],D[i]);
FOR(i,m,limit-1) D[i]=0;
}
void get_poly(int o,int l,int r){
if(l==r) return void((poly[o].push_back(b[l]?mod-b[l]:0),poly[o].push_back(1)));
//l=r时就是x-a_l
int mid=(l+r)>>1;
get_poly(lson);get_poly(rson); //分治两边
init(r-l+1);
NTT(poly[o<<1],poly[o<<1|1],poly[o]); //乘到自己这
}
void solve(vector<int> A,int o,int l,int r){
if(r-l<=100){ //常数（？）优化
FOR(i,l,r){
int s=0;
ROF(j,A.size()-1,0) s=add(1ll*s*b[i]%mod,A[j]); //直接秦九韶
ans[i]=s;
}
return;
}
vector<int> B;int mid=(l+r)>>1;
modulo(A,poly[o<<1],B,r-l,mid-l+1); //取模到左边
//此时A的次数应该<=r-l
solve(B,lson);
modulo(A,poly[o<<1|1],B,r-l,r-mid); //取模到右边
//因为A一开始的次数（就是n）可能巨小无比，甚至<r-l，所以在取模中要把高位补齐，不然可能越界
solve(B,rson);
}
int main(){
n=read();m=read();
FOR(i,0,n) a.push_back(read());
FOR(i,1,m) b[i]=read();
get_poly(1,1,m);
modulo(a,poly[1],a,n,m); //提前取模（注意！就是这里可能n<m，所以在取模中就要特判）
solve(a,1,1,m);
FOR(i,1,m) printf("%d\n",ans[i]);
}
```