文件详细信息

下载本文件

本文件的大小为 2196 字节。

#include<cstdio>
#include<cstring>
typedef long long ll;
const ll mod=998244353;
int read(){
	int ch=getchar(),num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
	return num;
}
void write(int a){
	if(a>=10)write(a/10);
	putchar(a%10|48);
}
ll qpow(ll a,int x=mod-2){
	if(x==0)return 1%mod;
	ll answer=1;
	while(x){
		if(x&1)answer=answer*a%mod;
		a=a*a%mod;
		x>>=1;
	}
	return answer;
}
void swap(ll&a,ll&b){
	ll temp=a;
	a=b;
	b=temp;
}
const int N=400005;
const ll G=3,invG=qpow(3),inv2=qpow(2);
int n;
ll a[N],b[N];
int rev[N];
void NTT(int n,ll*f,int type){
	for(int i=0;i<n;i++)
		if(i<rev[i])
			swap(f[i],f[rev[i]]);
	for(int p=2;p<=n;p<<=1){
		int len=p>>1;
		ll tG=qpow(type==1?G:invG,(mod-1)/p);
		for(int k=0;k<n;k+=p){
			ll buf=1;
			for(int l=k;l<k+len;l++){
				ll temp=buf*f[l+len]%mod;
				f[l+len]=((f[l]-temp)%mod+mod)%mod;
				f[l]=((f[l]+temp)%mod+mod)%mod;
				buf=buf*tG%mod;
			}
		}
	}
	if(type==-1){
		ll invn=qpow(n,mod-2);
		for(int i=0;i<n;i++)f[i]=f[i]*invn%mod;
	}
}
void poly_inv(ll*a,ll*b,int n){
	b[0]=qpow(a[0],mod-2);
	int len,limit;
	ll A[N],B[N];
    memset(A,0,sizeof(A));
    memset(B,0,sizeof(B));
	for(len=1;len<(n<<1);len<<=1){
		limit=len<<1;
		for(int i=0;i<len;i++)A[i]=a[i],B[i]=b[i];
		for(int i=0;i<limit;i++)rev[i]=(rev[i>>1]>>1)|((i&1)?len:0);
		NTT(limit,A,1);NTT(limit,B,1);
		for(int i=0;i<limit;i++)b[i]=((2ll-A[i]*B[i]%mod)*B[i]%mod+mod)%mod;
		NTT(limit,b,-1);
		for(int i=len;i<limit;i++)b[i]=0;
	}
	for(int i=n;i<len;i++)b[i]=0;
}
void poly_sqrt(ll*a,ll*b,int n){
	b[0]=1;
	ll A[N],B[N];
	memset(A,0,sizeof(A));
	memset(B,0,sizeof(B));
	int limit,len;
	for(len=1;len<(n<<1);len<<=1){
		limit=len<<1;
		for(int i=0;i<len;i++)A[i]=a[i];
		poly_inv(b,B,len);
		for(int i=0;i<limit;i++)rev[i]=(rev[i>>1]>>1)|((i&1)?len:0);
		NTT(limit,A,1),NTT(limit,B,1);
		for(int i=0;i<limit;i++)A[i]=A[i]*B[i]%mod;
		NTT(limit,A,-1);
		for(int i=0;i<len;i++)b[i]=(b[i]+A[i])%mod*inv2%mod;
		for(int i=len;i<limit;i++)b[i]=0;
	}
	for(int i=n;i<len;i++)b[i]=0; 
}
int main(){
	n=read();
	for(int i=0;i<n;i++)a[i]=read();
	poly_sqrt(a,b,n);
	for(int i=0;i<n;i++)write(b[i]),putchar(' ');
	return 0;
}