Home Article Practice 多项式多点求值,模板

多项式多点求值,模板

2022-05-11 16:48  views:427  source:Coat    

#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2
&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
R int res,f=1;R char ch;
while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
return res*f;
}
char sr[1<<21],z[20];int C=-1,Z=0;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
void print(R int x){
if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
while(z[++Z]=x%10+48,x/=10);
while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=(1<<17)+5,P=998244353;
inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R int y){
R int res=1;
for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;
return res;
}
int r[19][N],w[2][N],lg[N],inv[19];
void Pre(){
fp(d,1,17){
fp(i,1,(1<<d)-1)r[d][i]=(r[d][i>>1]>>1)|((i&1)<<(d-1));
lg[1<<d]=d,inv[d]=ksm(1<<d,P-2);
}
for(R int t=(P-1)>>1,i=1,x,y;i<131072;i<<=1,t>>=1){
x=ksm(3,t),y=ksm(332748118,t),w[0][i]=w[1][i]=1;
fp(k,1,i-1)
w[1][k+i]=mul(w[1][k+i-1],x),
w[0][k+i]=mul(w[0][k+i-1],y);
}
}
int lim,d,n,m;
inline void init(R int len){lim=1,d=0;while(lim<len)lim<<=1,++d;}
void NTT(int *A,int ty){
fp(i,0,lim-1)if(i<r[d][i])swap(A[i],A[r[d][i]]);
for(R int mid=1;mid<lim;mid<<=1)
for(R int j=0,t;j<lim;j+=(mid<<1))
fp(k,0,mid-1)
A[j+k+mid]=dec(A[j+k],t=mul(w[ty][mid+k],A[j+k+mid])),
A[j+k]=add(A[j+k],t);
if(!ty)fp(i,0,lim-1)A[i]=mul(A[i],inv[d]);
}
void Inv(int *a,int *b,int len){
if(len==1)return b[0]=ksm(a[0],P-2),void();
Inv(a,b,len>>1),lim=(len<<1),d=lg[lim];
static int A[N],B[N];
fp(i,0,len-1)A[i]=a[i],B[i]=b[i];fp(i,len,lim-1)A[i]=B[i]=0;
NTT(A,1),NTT(B,1);
fp(i,0,lim-1)A[i]=mul(A[i],mul(B[i],B[i]));
NTT(A,0);
fp(i,0,len-1)b[i]=dec(add(b[i],b[i]),A[i]);
fp(i,len,lim-1)b[i]=0;
}
struct node{
node *lc,*rc;vector<int>vec;int deg;
void Mod(const int *a,int *r,int n){
static int A[N],B[N],D[N];
int len=1;while(len<=n-deg)len<<=1;
fp(i,0,n)A[i]=a[n-i];fp(i,0,deg)B[i]=vec[deg-i];
fp(i,n-deg+1,len-1)B[i]=0;
Inv(B,D,len);
lim=(len<<1),d=lg[lim];
fp(i,n-deg+1,lim-1)A[i]=D[i]=0;
NTT(A,1),NTT(D,1);
fp(i,0,lim-1)A[i]=mul(A[i],D[i]);
NTT(A,0);
reverse(A,A+n-deg+1);
init(n+1);
fp(i,n-deg+1,lim-1)A[i]=0;
fp(i,0,deg)B[i]=vec[i];fp(i,deg+1,lim-1)B[i]=0;
NTT(A,1),NTT(B,1);
fp(i,0,lim-1)A[i]=mul(A[i],B[i]);
NTT(A,0);
fp(i,0,deg-1)r[i]=dec(a[i],A[i]);
}
void Mul(){
static int A[N],B[N];deg=lc->deg+rc->deg,vec.resize(deg+1),init(deg+1);
fp(i,0,lc->deg)A[i]=lc->vec[i];fp(i,lc->deg+1,lim-1)A[i]=0;
fp(i,0,rc->deg)B[i]=rc->vec[i];fp(i,rc->deg+1,lim-1)B[i]=0;
NTT(A,1),NTT(B,1);
fp(i,0,lim-1)A[i]=mul(A[i],B[i]);
NTT(A,0);
fp(i,0,deg)vec[i]=A[i];
}
}pool[N],*rt;
int A[N],a[N],tot;
inline node* newnode(){return &pool[tot++];}
void solve(node* &p,int l,int r){
p=newnode();
if(l==r)return p->deg=1,p->vec.resize(2),p->vec[0]=P-a[l],p->vec[1]=1,void();
int mid=(l+r)>>1;
solve(p->lc,l,mid),solve(p->rc,mid+1,r);
p->Mul();
}
int b[25];
void calc(node* p,int l,int r,const int *A){
if(r-l<=512){
fp(i,l,r){
int x=a[i],c1,c2,c3,c4,now=A[r-l];
b[0]=1;fp(j,1,16)b[j]=mul(b[j-1],x);
for(R int j=r-l-1;j-15>=0;j-=16){
c1=(1ll*now*b[16]+1ll*A[j]*b[15]+1ll*A[j-1]*b[14]+1ll*A[j-2]*b[13])%P,
c2=(1ll*A[j-3]*b[12]+1ll*A[j-4]*b[11]+1ll*A[j-5]*b[10]+1ll*A[j-6]*b[9])%P,
c3=(1ll*A[j-7]*b[8]+1ll*A[j-8]*b[7]+1ll*A[j-9]*b[6]+1ll*A[j-10]*b[5])%P,
c4=(1ll*A[j-11]*b[4]+1ll*A[j-12]*b[3]+1ll*A[j-13]*b[2]+1ll*A[j-14]*b[1])%P,
now=(0ll+c1+c2+c3+c4+A[j-15])%P;
}
fd(j,(r-l)%16-1,0)now=(1ll*now*x+A[j])%P;
print(now);
}
return;
}
int mid=(l+r)>>1,b[p->deg+1];
p->lc->Mod(A,b,p->deg-1),calc(p->lc,l,mid,b);
p->rc->Mod(A,b,p->deg-1),calc(p->rc,mid+1,r,b);
}
int main(){
// freopen("testdata.in","r",stdin);
n=read(),m=read();if(!m)return 0;
Pre();
fp(i,0,n)A[i]=read();
fp(i,1,m)a[i]=read();
solve(rt,1,m);
if(n>=m)rt->Mod(A,A,n);
calc(rt,1,m,A);
return Ot(),0;
}



Disclaimer: The above articles are added by users themselves and are only for typing and communication purposes. They do not represent the views of this website, and this website does not assume any legal responsibility. This statement is hereby made! If there is any infringement of your rights, please contact us promptly to delete it.

字符:    改为:
去打字就可以设置个性皮肤啦!(O ^ ~ ^ O)