Home Article Practice 多项式快速插值,模板

多项式快速插值,模板

2022-05-11 16:47  views:437  source:Coat    

#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
}
const int mod=998244353,N=262145+10;
namespace Poly{
int a[N],b[N],c[N],d[N],e[N],g[N],f2[N],rev[N],p[N],ans[N],qq[N],lim;
unsigned ll s[N];
inline int qpow(int x,int y){
int res=1;
while(y){
if(y&1) res=1ll*res*x%mod;
x=1ll*x*x%mod;
y>>=1;
}
return res;
}
inline void init(int mxn){
int l=0;
lim=1;
while(lim<mxn)
lim<<=1,l++;
for(int i=1;i<lim;i++)
rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
int xx=qpow(3,mod>>l);
p[lim>>1]=1;
for(int i=lim/2+1;i<lim;i++)
p[i]=1ll*p[i-1]*xx%mod;
for(int i=lim/2-1;i>0;i--)
p[i]=p[i<<1];
}
inline int getL(int mxn){
return 1<<32-__builtin_clz(mxn);
}
inline void DFT(int *a,int len){
int x=__builtin_ctz(lim/len);
for(int i=0;i<len;i++)
s[i]=a[rev[i]>>x];
for(int i=1;i!=len;i<<=1){
int dg=i<<1;
for(int j=0;j!=len;j+=dg){
for(int k=0;k<i;k++){
int t1=s[i|j|k]*p[i|k]%mod;
s[i|j|k]=s[j|k]+mod-t1;
s[j|k]+=t1;
}
}
}
for(int i=0;i<len;i++)
a[i]=s[i]%mod;
}
inline void IDFT(int *a,int len){
reverse(a+1,a+len);
DFT(a,len);
for(int i=0;i<len;i++)
a[i]=1ll*a[i]*(mod-mod/len)%mod;
}
inline void Inv(int n,int *a,int *b){
qq[0]=qpow(a[0],mod-2);
memset(c,0,sizeof(c));
memset(d,0,sizeof(d));
for(int dg=1;dg<n;dg<<=1){
for(int i=0;i<(dg<<1)&&i<n;i++)
c[i]=a[i];
for(int i=0;i<dg;i++)
d[i]=qq[i];
DFT(c,dg<<1),DFT(d,dg<<1);
for(int i=0;i<(dg<<1);i++)
c[i]=1ll*c[i]*d[i]%mod;
IDFT(c,dg<<1);
for(int i=0;i<dg;i++)
c[i]=0;
DFT(c,dg<<1);
for(int i=0;i<(dg<<1);i++)
c[i]=1ll*c[i]*d[i]%mod;
IDFT(c,dg<<1);
for(int i=dg;i<(dg<<1);i++)
qq[i]=1ll*c[i]*(mod-1)%mod;
}
for(int i=0;i<n;i++)
b[i]=qq[i];
}
inline void mul(int *a,int *b,int *s,int n,int m){
int len=getL(n+m-1);
static int c[N],d[N],e[N];
memset(c,0,len<<2);
memset(d,0,len<<2);
for(int i=0;i<n;i++)
c[i]=a[i];
for(int i=0;i<m;i++)
d[i]=b[i];
DFT(c,len),DFT(d,len);
for(int i=0;i<len;i++)
c[i]=1ll*c[i]*d[i]%mod;
IDFT(c,len);
for(int i=0;i<n+m-1;i++)
s[i]=c[i];
}
inline void mul2(int *a,int *b,int *s,int n,int m){
int len=getL(n);
static int c[N],d[N],e[N];
memset(c,0,len<<2);
memset(d,0,len<<2);
for(int i=0;i<n;i++)
c[i]=a[i];
for(int i=0;i<m;i++)
d[i]=b[m-i-1];
DFT(c,len),DFT(d,len);
for(int i=0;i<len;i++)
e[i]=1ll*c[i]*d[i]%mod;
IDFT(e,len);
for(int i=0;i<n-m+1;i++)
s[i]=e[m-1+i];
}
inline void Der(int *a,int *b,int n){
for(int i=1;i<n;i++)
b[i-1]=1ll*i*a[i]%mod;
b[n-1]=0;
}
int n,m,f[N],q[N],*t[N],*t2[N],buf[N<<5],*now=buf,sz[N],x[N],y[N];
inline void build(int l,int r,int rt){
t[rt]=now,now+=r-l+2,t2[rt]=now,now+=r-l+2;
if(l==r){
t[rt][0]=1;
t[rt][1]=x[l]?mod-x[l]:0;
return ;
}
int mid=l+r>>1,ls=rt<<1,rs=rt<<1|1;
build(l,mid,ls),build(mid+1,r,rs);
mul(t[ls],t[rs],t[rt],mid-l+2,r-mid+1);
}
inline void solve(int l,int r,int rt,int *a){
if(l==r){
a[l]=t2[rt][0];
return ;
}
int mid=l+r>>1,ls=rt<<1,rs=rt<<1|1;
mul2(t2[rt],t[rs],t2[ls],r-l+1,r-mid+1);
solve(l,mid,ls,a);
mul2(t2[rt],t[ls],t2[rs],r-l+1,mid-l+2);
solve(mid+1,r,rs,a);
}
int tmp1[N],tmp2[N],tmp3[N],tmp4[N],answ[N],*stein[N];
inline void interpolation(int rt,int l,int r){
stein[rt]=new int[r-l+1];
if(l==r){
stein[rt][0]=answ[l];
return ;
}
int mid=l+r>>1;
interpolation(rt<<1,l,mid),interpolation(rt<<1|1,mid+1,r);
int len=getL(r-l+1);
for(int i=0;i<mid-l+1;i++)
tmp3[i]=stein[rt<<1][i];
for(int i=0;i<r-mid;i++)
tmp4[i]=stein[rt<<1|1][i];
mul(t[rt<<1|1],tmp3,tmp3,r-mid+1,mid-l+1);
mul(t[rt<<1],tmp4,tmp4,mid-l+1+1,r-mid);
for(int i=0;i<=r-l;i++)
stein[rt][i]=(tmp3[i]+tmp4[i])%mod;
}
inline void Interpolation(int *x,int *y,int *ans,int n){
int len=getL(n);
build(1,n,1);
for(int i=0;i<=n;i++)
tmp1[i]=t[1][i];
reverse(tmp1,tmp1+n+1);
Der(tmp1,tmp1,n+1);
Inv(n+1,t[1],tmp2);
mul2(tmp1,tmp2,t2[1],n*2-1,n);
solve(1,n,1,answ);
for(int i=1;i<=n;i++)
answ[i]=1ll*y[i]*qpow(answ[i],mod-2)%mod;
interpolation(1,1,n);
for(int i=0;i<n;i++)
ans[i]=stein[1][n-1-i];
}
}
using namespace Poly;
int F[N];
int main(){
n=read()+1;
init(n<<1);
for(int i=1;i<=n;i++)
x[i]=read(),y[i]=read();
Interpolation(x,y,F,n);
for(int i=0;i<n;i++)
write(F[i]),putc(' ');
flush();
return 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)