记录编号	440534	评测结果	AAAAAAAAAA
题目名称	多项式插值Ⅱ	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	5.406 s
提交时间	2017-08-23 11:33:10	内存使用	8.88 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+10,p=119<<23|1;
int inc(int x,int y){x+=y;return x>=p?x-p:x;}
int dec(int x,int y){x-=y;return x<0?x+p:x;}
int mul(int x,int y){return (ll)x*y%p;}
int power(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=mul(x,x))
		if (y&1) ans=mul(ans,x);
	return ans;
}
int w[N],iw[N];
void init(int n){
	w[0]=1;w[1]=power(3,(p-1)/n);
	for (int i=2;i<=n;i++) w[i]=mul(w[i-1],w[1]);
	for (int i=0;i<=n;i++) iw[i]=w[n-i];
}
void fft(int n,int *a,int *w){
	for (int i=0,j=0;i<n;i++){
		if (i<j) swap(a[i],a[j]);
		for (int k=n>>1;(j^=k)<k;k>>=1);
	}
	for (int i=2;i<=n;i<<=1){
		int m=i>>1,step=n/i;
		for (int j=0;j<n;j+=i)
		for (int k=0,pos=0;k<m;k++,pos+=step){
			int t=mul(a[j+k+m],w[pos]);
			a[j+k+m]=dec(a[j+k],t);
			a[j+k]=inc(a[j+k],t);
		}
	}
	if (w==iw){
		int del=power(n,p-2);
		for (int i=0;i<n;i++) a[i]=mul(a[i],del);
	}
}
void getinv(int n,int *a,int *b){
	if (n==1) return void(b[0]=power(a[0],p-2));
	getinv((n+1)>>1,a,b);
	static int tmp[N];
	int size=1;
	while (size<n+n) size<<=1;
	init(size);
	for (int i=0;i<n;i++) tmp[i]=a[i];
	for (int i=n;i<size;i++) tmp[i]=0;
	fft(size,tmp,w);fft(size,b,w);
	for (int i=0;i<size;i++) b[i]=mul(b[i],dec(2,mul(b[i],tmp[i])));
	fft(size,b,iw);
	for (int i=n;i<size;i++) b[i]=0;
}
void getmod(int n,int *a,int m,int *b,int *c){
	static int tmp[N],inv[N];
	int size=1;
	while (size<n+n) size<<=1;
	for (int i=0;i<size;i++) tmp[i]=inv[i]=0;
	for (int i=0;i<m;i++) tmp[i]=b[m-i-1];
	getinv(n-m+1,tmp,inv);
	for (int i=0;i<size;i++) tmp[i]=0;
	for (int i=0;i<n;i++) tmp[i]=a[n-i-1];
	init(size);
	fft(size,tmp,w);fft(size,inv,w);
	for (int i=0;i<size;i++) inv[i]=mul(tmp[i],inv[i]);
	fft(size,inv,iw);
	for (int i=n-m+1;i<size;i++) inv[i]=0;
	reverse(inv,inv+n-m+1);
	for (int i=0;i<m;i++) tmp[i]=b[i];
	for (int i=m;i<size;i++) tmp[i]=0;
	fft(size,tmp,w);fft(size,inv,w);
	for (int i=0;i<size;i++) tmp[i]=mul(tmp[i],inv[i]);
	fft(size,tmp,iw);
	for (int i=0;i<m;i++) c[i]=dec(a[i],tmp[i]);
}
int *k[N];
#define lc x<<1
#define rc x<<1|1
void build(int x,int n,int *X){
	k[x]=new int[n+1];
	if (n==1){
		k[x][0]=dec(0,X[0]);
		k[x][1]=1;
		return;
	}
	static int L[N],R[N];
	int m=n>>1;
	build(lc,m,X);
	build(rc,n-m,X+m);
	int size=1;
	while (size<=n) size<<=1;
	for (int i=0;i<size;i++) L[i]=R[i]=0;
	for (int i=0;i<=m;i++) L[i]=k[lc][i];
	for (int i=0;i<=n-m;i++) R[i]=k[rc][i];
	init(size);
	fft(size,L,w);fft(size,R,w);
	for (int i=0;i<size;i++) L[i]=mul(L[i],R[i]);
	fft(size,L,iw);
	for (int i=0;i<=n;i++) k[x][i]=L[i];
}
void calc(int x,int n,int *f,int *X,int *y){
	if (n==1) return void(y[0]=f[0]);
	if (n<=60){
		for (int i=0;i<n;i++){
			int now=0;
			for (int j=n-1;j>=0;j--) now=inc(mul(now,X[i]),f[j]);
			y[i]=now;
		}
		return;
	}
	int m=n>>1;
	int *mod=new int[n+1];
	for (int i=0;i<=n;i++) mod[i]=0;
	getmod(n,f,m+1,k[lc],mod);
	calc(lc,m,mod,X,y);
	for (int i=0;i<=n;i++) mod[i]=0;
	getmod(n,f,n-m+1,k[rc],mod);
	calc(rc,n-m,mod,X+m,y+m);
}
void combine(int x,int n,int **k,int *y,int *f){
	if (n==1) return void(f[0]=y[0]);
	int size=1;
	while (size<n) size<<=1;
	static int L[N],R[N];
	int *fl=new int[size],*fr=new int[size];
	for (int i=0;i<size;i++) fl[i]=fr[i]=0;
	int m=n>>1;
	combine(lc,m,k,y,fl);
	combine(rc,n-m,k,y+m,fr);
	for (int i=0;i<size;i++) L[i]=R[i]=0;
	for (int i=0;i<=m;i++) L[i]=k[lc][i];
	for (int i=0;i<=n-m;i++) R[i]=k[rc][i];
	init(size);
	fft(size,L,w);fft(size,R,w);fft(size,fl,w);fft(size,fr,w);
	for (int i=0;i<size;i++) f[i]=inc(mul(fl[i],R[i]),mul(fr[i],L[i]));
	fft(size,f,iw);
}
int n,f[N],x[N],y[N],M[N],My[N];
int main()
{
	freopen("interpolation2.in","r",stdin);
	freopen("interpolation2.out","w",stdout);
	scanf("%d",&n);
	for (int i=0;i<n;i++) scanf("%d%d",&x[i],&y[i]);
	build(1,n,x);
	for (int i=0;i<n;i++) M[i]=mul(k[1][i+1],i+1);
	calc(1,n,M,x,My);
	for (int i=0;i<n;i++) y[i]=mul(y[i],power(My[i],p-2));
	combine(1,n,k,y,f);
	for (int i=0;i<n;i++) printf("%d ",f[i]);puts("");
	return 0;
}