文件详细信息

下载本文件

本文件的大小为 2223 字节。

//这份代码常数很大，只能过前 $7$ 个数据点。
#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;
}
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;
}
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]=((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_mul(ll*f,ll*g,ll*h,int n,int m){
	int limit=n;
	for(m+=limit,limit=1;limit<=m;limit<<=1);
	for(int i=0;i<limit;i++)rev[i]=(rev[i>>1]>>1)|((i&1)?limit>>1:0);
	NTT(limit,f,true);
	if(f!=g)NTT(limit,g,true);
	for(int i=0;i<limit;i++)f[i]=f[i]*g[i]%mod;
	NTT(limit,f,false);
	ll invn=qpow(limit);
	for(int i=0;i<n;i++)h[i]=((f[i]*invn%mod+mod)%mod);
}
void poly_pow(ll*a,ll*b,int n,int k){
	ll temp[N],newa[N],newb[N];
	memset(b,0,sizeof(b));
	b[0]=1;
	while(k){
		if(k&1){
			memset(temp,0,sizeof(temp));
			memcpy(newa,a,sizeof(newa));
			memcpy(newb,b,sizeof(newb));
			poly_mul(newb,newa,temp,n,n);
			for(int i=0;i<n;i++)b[i]=temp[i];
		}
		memcpy(newa,a,sizeof(newa));
		memset(temp,0,sizeof(temp));
		poly_mul(newa,newa,temp,n,n);
		for(int i=0;i<n;i++)a[i]=temp[i];
		k>>=1;
	}
}
int n,k;
ll f[N],g[N];
int main(){
	n=read(),k=readk();
	for(int i=0;i<n;i++)f[i]=read();
	poly_pow(f,g,n,k);
	for(int i=0;i<n;i++)write(g[i]),putchar(' ');
	return 0;
}