文件详细信息

下载本文件

本文件的大小为 1664 字节。

#include<cstdio>
#include<cstring>
template<typename T>
void read(T&num){
	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();
}
template<typename T>
void write(T a){
	static int ch[20],cnt=0;
	if(a==0)putchar('0');
	while(a)ch[cnt++]=a%10|48,a/=10;
	while(cnt)putchar(ch[--cnt]);
}
template<typename T>
void swap(T&a,T&b){
	T temp=a;
	a=b;
	b=temp;
}
typedef long long ll;
const ll P=998244353;
ll qpow(ll a,int x){
	ll ans=1;
	while(x){
		if(x&1)ans=ans*a%P;
		a=a*a%P;
		x>>=1;
	}
	return ans;
}
const int maxn=100000;
const ll G=3,invG=qpow(G,P-2);
int n,tr[1<<18];
ll a[1<<18],b[1<<18];
void NTT(int n,ll*f,int type){
	for(int i=0;i<n;i++)
		if(i<tr[i])
			swap(f[i],f[tr[i]]);
	for(int p=2;p<=n;p<<=1){
		int len=p>>1;
		ll tG=qpow(type==1?G:invG,(P-1)/p);
		for(int k=0;k<n;k+=p){
			ll buf=1;
			for(int l=k;l<k+len;l++){
				ll tmp=buf*f[l+len]%P;
				f[l+len]=(P+f[l]-tmp)%P;
				f[l]=(f[l]+tmp)%P;
				buf=buf*tG%P;
			}
		}
	}
	if(type==-1){
		ll invn=qpow(n,P-2);
		for(int i=0;i<n;i++)f[i]=f[i]*invn%P;
	}
}
void poly_inv(ll*a,ll*b,int n){
	static ll c[1<<18];
	if(n==1){
		b[0]=qpow(a[0],P-2);
		return;
	}
	poly_inv(a,b,(n+1)>>1);
	int len=1;
	while(len<(n<<1))len<<=1;
	for(int i=0;i<len;i++)tr[i]=(tr[i>>1]>>1)|((i&1)?(len>>1):0);
	memcpy(c,a,sizeof(ll)*n);
	memset(c+n,0,sizeof(ll)*(len-n));
	NTT(len,b,1),NTT(len,c,1);
	for(int i=0;i<len;i++)b[i]=(P+2-b[i]*c[i]%P)*b[i]%P;
	NTT(len,b,-1);
	memset(b+n,0,sizeof(ll)*(len-n));
}
int main(){
	read(n);
	for(int i=0;i<n;i++)read(a[i]);
	poly_inv(a,b,n);
	for(int i=0;i<n;i++)write(b[i]),putchar(i!=n-1?' ':'\n');
	return 0;
}