文件详细信息

下载本文件

本文件的大小为 2660 字节。

#include<cstdio>
#include<cstring>
typedef long long ll;
const ll mod=998244353;
const int N=400005;
int rev[N];
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 ll G=3,invG=qpow(3),inv2=qpow(2);
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]=(mod+f[l]-temp)%mod;
				f[l]=(f[l]+temp)%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]=(mod+2ll-A[i]*B[i]%mod)*B[i]%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_mul(ll*f,ll*g,ll*h,int n,int m){
	for(m+=n,n=1;n<=m;n<<=1);
	for(int i=0;i<n;i++)rev[i]=(rev[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(n,f,true),NTT(n,g,true);
	for(int i=0;i<n;i++)f[i]=f[i]*g[i]%mod;
	NTT(n,f,-1);
	for(int i=0;i<n;i++)h[i]=f[i];
}
void derivation(ll*a,ll*b,int n){
	for(int i=1;i<n;i++)b[i-1]=i*a[i]%mod;
	b[n-1]=0;
}
void integral(ll*a,ll*b,int n){
	for(int i=1;i<n;i++)b[i]=a[i-1]*qpow(i,mod-2)%mod;
	b[0]=0;
}
ll a1[N],a2[N],b1[N];
void poly_ln(ll*a,ll*b,int n){
	derivation(a,a1,n);
	poly_inv(a,a2,n);
	poly_mul(a1,a2,b1,n,n);
	integral(b1,b,n);
}
ll lnb[400005];
void poly_exp(ll*a,ll*b,int n){
	if(n==1){
		b[0]=1;
		return;
	}
	poly_exp(a,b,(n+1)>>1);
	poly_ln(b,lnb,n);
	int m=1;
	for(;m<(n<<1);m<<=1);
	for(int i=0;i<m;i++)rev[i]=(rev[i>>1]>>1)|((i&1)?(m>>1):0);
	for(int i=0;i<n;i++)lnb[i]=(a[i]-lnb[i]+mod)%mod;
	for(int i=n;i<m;i++)lnb[i]=b[i]=0;
	lnb[0]++;
	NTT(m,lnb,1),NTT(m,b,1);
	for(int i=0;i<m;i++)b[i]=b[i]*lnb[i]%mod;
	NTT(m,b,-1);
	for(int i=n;i<m;i++)b[i]=0;
}
int n;
ll f[N],g[N];
int main(){
	n=read();
	for(int i=0;i<n;i++)f[i]=read();
	poly_exp(f,g,n);
	for(int i=0;i<n;i++)write(g[i]),putchar(' ');
	return 0;
}