文件详细信息

下载本文件

本文件的大小为 2820 字节。

#include<cstdio>
#include<cstring>
typedef long long ll;
const ll mod=998244353;
const int N=500005;
int n,k;
ll a[N],lna[N],b[N],G[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;
}
int readk(){
	int ch=getchar();
	ll num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=((num<<3)+(num<<1)+(ch^48))%mod,ch=getchar();
	return num;
}
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;
}
int rev[N];
const ll invG=qpow(3),inv2=qpow(2);
void NTT(ll*f,int type,int n){
	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?3: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==0){
		ll invn=qpow(n,mod-2);
		for(int i=0;i<n;i++)f[i]=f[i]*invn%mod;
	}
}
ll A[N],B[N];
void poly_inv(ll*a,ll*b,int n){
	b[0]=qpow(a[0],mod-2);
	int len,limit;
	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(A,1,limit);NTT(B,1,limit);
		for(int i=0;i<limit;i++)b[i]=((2ll-A[i]*B[i]%mod)*B[i]%mod+mod)%mod;
		NTT(b,0,limit);
		for(int i=len;i<limit;i++)b[i]=0;
	}
	for(int i=n;i<len;i++)b[i]=0;
}
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 c[N];
void poly_ln(ll*a,ll*b,int n){
	derivation(a,c,n),poly_inv(a,b,n);
	int lim,l=-1;
	for(lim=1;lim<(n<<1);lim<<=1)++l;
	for(int i=1;i<lim;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<l);
	for(int i=n;i<lim;++i)b[i]=c[i]=0;
	NTT(c,1,lim),NTT(b,1,lim);
	for(int i=0;i<lim;++i)c[i]=b[i]*c[i]%mod;
	NTT(c,0,lim);
	integral(c,b,n);
	for(int i=n;i<lim;++i)b[i]=0;
}
ll lnb[N];
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(lnb,1,m),NTT(b,1,m);
	for(int i=0;i<m;i++)b[i]=b[i]*lnb[i]%mod;
	NTT(b,0,m);
	for(int i=n;i<m;i++)b[i]=0;
}
int main(){
	n=read(),k=readk();
	for(int i=0;i<n;++i)a[i]=read();
	poly_ln(a,lna,n);
	for(int i=0;i<n;++i)lna[i]=lna[i]*(ll)k%mod;
	poly_exp(lna,b,n);
	for(int i=0;i<n;++i)printf("%lld ",b[i]);
	return 0;
}