C++ 解法, 执行用时: 1559ms, 内存消耗: 23940K, 提交时间: 2022-02-18 22:34:23

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int N=2e5+5,maxn=1<<23;
ll c[N],mi[N],ans[maxn],f[maxn],g[maxn],pre[N],suf[N];
int rv[maxn],m,st;
ll ksm(ll x,ll y){
	ll res=1;
	while (y){
		if (y&1) res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
void NTT(ll *f,int n,int rev){
	for (int i=0;i<n;++i) if (rv[i]<i) swap(f[i],f[rv[i]]);
//	for (int i=0;i<n;++i) printf("%lld ",f[i]);printf("\n");
	for (int L=2;L<=n;L<<=1){
		ll step=ksm(3ll,(mod-1)/L);
		for (int i=0;i<n;i+=L){
			ll cur=1ll;
			for (int k=0;k<(L>>1);++k){
				ll t=f[i+k+(L>>1)]*cur%mod;
				f[i+k+(L>>1)]=(f[i+k]-t+mod)%mod;
				f[i+k]=(f[i+k]+t)%mod;
				cur=cur*step%mod;
			}
		}
	}
	if (rev==-1){
		reverse(f+1,f+n);
		ll t=ksm(n,mod-2);
		for (int i=0;i<n;++i) f[i]=f[i]*t%mod;
	}
}
void divide(int l,int r){
	if (l==r) return;
	int mid=l+r>>1;
	divide(l,mid);
	divide(mid+1,r);
	int len;
	for (len=1;len<2*(r-l+1);len<<=1);
	for (int i=0;i<len;++i) f[i]=g[i]=0;
	ll tmp=1;
	for (int i=mid;i>=l;--i){
		f[i-l]=tmp*(i==0?1:pre[i-1])%mod;
		tmp=(mi[i]-1+mod)%mod*tmp%mod;
	}
	tmp=1;
	for (int i=mid+1;i<=r;++i){
		g[i-(mid+1)]=tmp*(i==st?1:suf[i+1])%mod;
		tmp=(mi[i]-1+mod)%mod*tmp%mod;
	}
	for (int i=0;i<len;++i) rv[i]=(rv[i>>1]>>1)+(i&1)*(len>>1);
	NTT(f,len,1);
	NTT(g,len,1);
	for (int i=0;i<len;++i) f[i]=f[i]*g[i]%mod;
	NTT(f,len,-1);
	for (int i=0;i<len;++i)
		if (f[i]) (ans[l+mid+1+i]+=f[i])%=mod;
}
int main(){
	int k;
	scanf("%d%d",&m,&k);st=m+1;
	for (int i=0;i<=m;++i){
		scanf("%lld",&c[i]);
		mi[i]=ksm(2,c[i]);
		if (!c[i] && st==m+1) st=i;
	}
	ll BASE=1;
	for (int i=st+1;i<=m;++i) BASE=BASE*mi[i]%mod;
	if (st==0){
		printf("%lld ",BASE);
		for (int i=1;i<=k;++i) printf("0 ");
		return 0;
	}
	pre[0]=(mi[0]-2+mod);
	for (int i=1;i<st;++i) pre[i]=(mi[i]-2+mod)%mod*pre[i-1]%mod;
	suf[st]=1;
	for (int i=st-1;i>=0;--i) suf[i]=suf[i+1]*mi[i]%mod;
	divide(0,st);
	ll tmp=1;
	for (int i=0;i<st;++i) tmp=(mi[i]-2+mod)%mod*tmp%mod;
	for (int i=0;i<=k;++i) ans[i]=ans[i]*2%mod;
	(ans[2*st]+=tmp)%=mod;
	for (int i=0;i<=k;++i) printf("%lld ",ans[i]*BASE%mod);
	return 0;
}