代码

#include<bits/stdc++.h>
#define ll long long
#define vci vector<int>
using namespace std;
const int mod=998244353;
const int N=1<<21|5;
const int gen=3;
inline int fsp(int x,int y){
	int ans=1;for(;y;y>>=1,x=1ll*x*x%mod)(y&1)&&(ans=1ll*ans*x%mod);
	return ans;
}namespace Math{
	namespace Qr{
		mt19937 rnd(time(0));
		#define fst first
		#define snd second
		int w,a;
		pair<int,int> A,B;
		bool chk(int x){return fsp(x,mod-1>>1)==1;}
		inline void upda(){
			int x=A.fst,y=A.snd;
			A=make_pair((1ll*x*x+1ll*y*y%mod*w)%mod,2ll*x*y%mod);
		}inline void updb(){
			int x=B.fst,y=B.snd;
			B=make_pair((1ll*x*A.fst+1ll*y*A.snd%mod*w)%mod,(1ll*x*A.snd+1ll*y*A.fst)%mod);
		}int slv(int x){
			if(!chk(x))return -1;
			do{a=rnd()%mod;w=(1ll*a*a+mod-x)%mod;}while(chk(w));
			A=make_pair(a,1);B=make_pair(1,0);
			for(int y=mod+1>>1;y;upda(),y>>=1)
				y&1&&(updb(),0);
			return min(B.fst,mod-B.fst);
		}
		#undef fst
		#undef snd
	}
	int tr=0,tw=2,tv=2,rev[N],w[N],iv[N];
	inline void initrev(int x){
		tr=x;for(int i=0;i<x;i++)rev[i]=rev[i>>1]>>1|((i&1)?x>>1:0);
	}inline void initw(int x){(!w[1])&&(w[1]=1);
		for(;tw<x;tw<<=1){
			w[tw]=1;w[tw+1]=fsp(gen,mod/(tw<<1));
			for(int i=tw+2;i<(tw<<1);++i)w[i]=1ll*w[i-1]*w[tw+1]%mod;
		}
	}inline void initiv(int x){(!iv[1])&&(iv[1]=1);
		for(;tv<=x;++tv)iv[tv]=1ll*(mod-mod/tv)*iv[mod%tv]%mod;
	}inline int ginv(int x){
		(x<=1<<21)&&(initiv(x),0);
		return x<tv?iv[x]:fsp(x,mod-2);
	}inline void ntt(int* a,int lim,int fl=1){
		static unsigned ll A[N];initw(lim);
		(tr!=lim)&&(initrev(lim),0);
		for(int i=0;i<lim;i++)A[rev[i]]=a[i];
		for(int k=1;k<lim;k<<=1){
			if(k==1<<18)for(int i=0;i<lim;++i)A[i]%=mod;
			for(int j=0;j<lim;j+=k<<1)for(int i=j,t;i<j+k;++i)
				A[i+k]=A[i]+mod-(t=A[i+k]*w[i+k-j]%mod),A[i]+=t;
		}if(fl^1){reverse(A+1,A+lim);for(int i=0,niv=ginv(lim);i<lim;i++)a[i]=A[i]*niv%mod;}
		else for(int i=0;i<lim;i++)a[i]=A[i]%mod;
	}
}namespace Poly{
	using Math::ntt;
	using Math::ginv;
	struct poly{
		vci f;
		poly(){f.clear();}
		poly(int x){f.clear();f.push_back(x);}
		poly(int *a,int n){f.resize(n);memcpy(f.data(),a,n<<2);}
		inline int operator [](int x)const{return x<f.size()?f[x]:0;}
		inline int& operator [](int x){return f.at(x);}
		inline int* data(){return f.data();}inline const int* data()const{return f.data();}
		inline int size()const{return f.size();}inline void resize(int x){return f.resize(x);}
		inline void copy(int *a,int len)const{
			memcpy(a,data(),min(len,size())<<2);
			len>size()&&(memset(a+size(),0,len-size()<<2));
		}inline void print(char ch=' ')const{
			for(int i=0;i<size();++i,putchar(ch))printf("%d",f[i]);putchar('\n');
		}inline poly slice(int len)const{poly a;a.resize(len);copy(a.data(),len);return a;}
		inline void reverse(){::reverse(f.begin(),f.end());}
		inline poly rev()const{poly a(*this);a.reverse();return a;}
		inline poly& operator +=(const poly& a){
			a.size()>size()&&(resize(a.size()),0);
			for(int i=0;i<a.size();i++)f[i]=(f[i]+a[i])%mod;
			return *this;
		}inline poly& operator -=(const poly& a){
			a.size()>size()&&(resize(a.size()),0);
			for(int i=0;i<a.size();i++)f[i]=(f[i]+mod-a[i])%mod;
			return *this;
		}inline poly operator +(const poly& a)const{poly b(*this);return b+=a;}
		inline poly operator -(const poly& a)const{poly b(*this);return b-=a;}
		inline poly& operator *=(const int& x){
			for(int i=0,n=size();i<n;i++)f[i]=1ll*f[i]*x%mod;
			return *this;
		}inline poly operator *(const int& x)const{poly b(*this);b*=x;return b;}
		inline poly& operator *=(const poly& a){
			static int A[N];
			int lim=1;while(lim<size()+a.size()-1)lim<<=1;
			resize(lim);memcpy(A,a.data(),a.size()<<2);ntt(data(),lim);ntt(A,lim);
			for(int i=0;i<lim;i++)f[i]=1ll*f[i]*A[i]%mod;
			ntt(data(),lim,0);memset(A,0,lim<<2);return *this;
		}inline poly operator *(const poly& a)const{poly b(*this);(b*=a).resize(size()+a.size()-1);return b;}
		inline poly mul(const poly& a)const{poly b(*this);(b*=a.slice(size())).resize(size());return b;}
		inline poly inv(int x=-1)const{
			static int A[N],B[N];
			poly a(ginv(f[0]));~x||(x=size());
			for(int i=1;i<x;i<<=1){
				memcpy(A,a.data(),i<<2);copy(B,i<<1);
				a.resize(i<<1);ntt(A,i<<1);ntt(B,i<<1);
				for(int j=0;j<(i<<1);j++)B[j]=mod-1ll*A[j]*B[j]%mod;
				ntt(B,i<<1,0);memset(B,0,i<<2);ntt(B,i<<1);
				for(int j=0;j<(i<<1);j++)B[j]=1ll*A[j]*B[j]%mod;
				ntt(B,i<<1,0);memcpy(a.data()+i,B+i,i<<2);
				((i<<1)<x)||(memset(A,0,i<<3),memset(B,0,i<<3),0);
			}a.resize(x);return a;
		}
		inline poly div(const poly& a)const{
			static int A[N],B[N],C[N];
			int len=2;while(len<size())len<<=1;
			a.inv(len>>1).copy(A,len>>1);copy(B,len>>1);ntt(A,len);ntt(B,len);
			for(int i=0;i<len;i++)B[i]=1ll*A[i]*B[i]%mod;ntt(B,len,0);
			memset(B+(len>>1),0,len<<1);poly b(B,len);a.copy(C,len);ntt(B,len);
			ntt(C,len);for(int i=0;i<len;i++)B[i]=1ll*B[i]*C[i]%mod;ntt(B,len,0);
			for(int i=0;i<size();i++)B[i]=(B[i]+mod-f[i])%mod;memset(B,0,len<<1);
			ntt(B,len);for(int i=0;i<len;i++)B[i]=mod-1ll*A[i]*B[i]%mod;
			ntt(B,len,0);memcpy(b.data()+(len>>1),B+(len>>1),len<<1);
			memset(A,0,len<<2);memset(B,0,len<<2);memset(C,0,len<<2);
			b.resize(size());return b;
		}inline poly der()const{
			poly a;a.resize(size()-1);
			for(int i=1;i<=a.size();i++)a[i-1]=1ll*i*f[i]%mod;
			return a;
		}inline poly ite()const{
			poly a;a.resize(size()+1);
			for(int i=size();i;i--)a[i]=1ll*ginv(i)*f[i-1]%mod;
			return a;
		}inline poly ln()const{return der().div(*this).ite();}
		inline poly exp(int x=-1)const{
			static int A[N],B[N];
			poly a(1);(~x)||(x=size());
			for(int i=1;i<x;i<<=1){
				memcpy(A,a.data(),i<<2);a.resize(i<<1);
				memcpy(B,(a.ln()-slice(i<<1)).data(),i<<3);
				ntt(A,i<<1);ntt(B,i<<1);
				for(int j=0;j<i<<1;j++)A[j]=mod-1ll*A[j]*B[j]%mod;
				ntt(A,i<<1,0);memcpy(a.data()+i,A+i,i<<2);
				(i<<1<x)||(memset(A,0,i<<3),memset(B,0,i<<3),0);
			}a.resize(x);return a;
		}inline poly& operator /=(const poly& a){
			if(a.size()>size())return (*this=poly(0));
			reverse();resize(size()-a.size()+1);
			*this=div(a.rev());reverse();
			return *this;
		}inline poly operator /(const poly& a)const{poly b(*this);return (b/=a);}
		inline poly& operator %=(const poly& a){operator -=(a*operator /(a));resize(a.size()-1);return *this;}
		inline poly operator %(const poly& a)const{poly b(*this);return (b%=a);}
		inline poly sqrt(int x=-1)const{
			static int A[N],B[N];
			poly a(Math::Qr::slv(f[0]));(~x)||(x=size());
			for(int i=1;i<x;i<<=1){
				memcpy(A,a.data(),i<<2);a.inv().copy(B,i);ntt(A,i);
				for(int j=0;j<i;j++)A[j]=1ll*A[j]*A[j]%mod;ntt(A,i,0);
				for(int j=0;j<i;j++)A[j]=(A[j]+mod-(j+i<x?(f[j]+f[i+j])%mod:f[j]))%mod;
				ntt(A,i<<1);ntt(B,i<<1);for(int j=0;j<i<<1;j++)A[j]=499122176ll*A[j]%mod*B[j]%mod;
				ntt(A,i<<1,0);a.resize(i<<1);memcpy(a.data()+i,A,i<<2);
				i<<1<x||(memset(A,0,i<<3),memset(B,0,i<<3),0);
			}a.resize(x);return a;
		}inline poly pow(int x=0)const{return (ln()*x).exp();}
	};
}
using Poly::poly;
int n,m;poly a,b,c;
int main(){
	scanf("%d%d",&n,&m);a.resize(++n);
	for(int i=0;i<n;i++)scanf("%d",&a[i]);
	b=a.sqrt().inv().ite();b.resize(n);a[0]=2;
	a-=b.exp();(a.ln()+1).pow(m).der().print();
	return 0;
}

评测结果