多项式快速插值,模板
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;
}