题解

题目分析

这是一道算法题目，需要根据具体题目要求进行求解。

解题思路

1. 问题分析

• 仔细阅读题目描述，理解题目要求
• 分析输入输出格式和约束条件
• 确定需要使用的算法和数据结构

2. 算法选择

• 根据题目特点选择合适的算法
• 考虑时间复杂度和空间复杂度
• 确保算法能正确处理所有测试用例

3. 实现要点

• 注意边界条件的处理
• 优化输入输出以提高效率
• 确保代码的正确性和鲁棒性

4. 调试和优化

• 使用测试用例验证算法正确性
• 分析性能瓶颈并进行优化
• 确保代码能通过所有测试点

注意事项

• 仔细处理数据类型和精度问题
• 注意数组越界和空指针问题
• 确保算法的时间复杂度符合要求

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=65540,mod=998244353,g=3,invg=(mod+1)/3,inv2=(mod+1)/2;
int rev[N],fac[N],ifac[N],p[N];
ull a[N],b[N],c[N],*d[N<<2],x[N],y[N],w[N],inv[N];
int qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1){
			ans=1ll*ans*a%mod;
		}
		a=1ll*a*a%mod;
		b>>=1;
	}
	return ans;
}
void CLR(ull *a,int n){
	for(int i=0;i<=n-1;i++){
		a[i]=0;
	}
}
void CPY(ull *a,ull *b,int n){
	for(int i=0;i<=n-1;i++){
		a[i]=b[i];
	}
}
void INIT(int lim){
	for(int i=0;i<lim;i++){
		rev[i]=(rev[i>>1]>>1)|((i&1)?lim>>1:0);
	}
}
void REV(ull *a,int n){
	reverse(a,a+n);
}
void ADD(ull *a,ull *b,int n){
	for(int i=0;i<=n-1;i++){
		a[i]=(a[i]+b[i])%mod;
	}
}
void DEC(ull *a,ull *b,int n){
	for(int i=0;i<=n-1;i++){
		a[i]=(a[i]-b[i]+mod)%mod;
	}
}
void DRV(ull *a,int n){
	for(int i=0;i<=n-1;i++){
		a[i]=a[i+1]*(i+1)%mod;
	}
}
void ITG(ull *a,int n){
	for(int i=n-1;i>=1;i--){
		a[i]=a[i-1]*inv[i]%mod;
	}
	a[0]=0;
}
void NTT(ull *a,int lim,int op){
	ull x,y;
	int r;
	for(int i=0;i<lim;i++){
		if(i<rev[i]){
			swap(a[i],a[rev[i]]);
		}
	}
	w[0]=1;
	for(int mid=1;mid<lim;mid<<=1){
		r=mid<<1;
		x=qpow(op==1?g:invg,(mod-1)/r);
		for(int j=1;j<mid;j++){
			w[j]=w[j-1]*x%mod;
		}
		for(int j=0;j<lim;j+=r){
			for(int k=j;k-j<mid;k++){
				x=a[k];
				y=a[k+mid]%mod*w[k-j]%mod;
				a[k]=x+y;
				a[k+mid]=x-y+mod;
			}
		}
		if(mid==(1<<18)){
			for(int j=0;j<lim;j++){
				a[j]%=mod;
			}
		}
	}
	for(int i=0;i<lim;i++){
		a[i]%=mod;
	}
}
void CROSS(ull *a,ull *b,int n){
	for(int i=0;i<=n-1;i++){
		a[i]=a[i]*b[i]%mod;
	}
}
void MUL(ull *a,ull *b,int n){
	int lim=1,invv;
	while(lim<n){
		lim<<=1;
	}
	invv=qpow(lim,mod-2);
	INIT(lim);
	NTT(a,lim,1);
	if(a!=b){
		NTT(b,lim,1);
	}
	CROSS(a,b,lim);
	NTT(a,lim,-1);
	for(int i=0;i<lim;i++){
		a[i]=a[i]*invv%mod;
	}
	CLR(a+n,lim-n);
	if(a!=b){
		CLR(b,lim);
	}
}
void MULT(ull *a,ull *b,int n,int m){
	REV(b,m);
	MUL(a,b,n+m);
	for(int i=0;i<=n-1;i++){
		a[i]=a[i+m-1];
	}
	CLR(a+n,m);
}
void INV(ull *a,ull *b,int n){
	int lim=1,l=0,invv;
	static ull c[N],d[N];
	b[0]=qpow(a[0],mod-2);
	while(lim<n){
		lim<<=1;
		l++;
	}
	for(int len=2;len<=lim;len<<=1){
		CLR(c+(len>>1),len>>1);
		CPY(c,b,len>>1);
		CPY(d,a,len);
		INIT(len);
		NTT(c,len,1);
		NTT(d,len,1);
		CROSS(d,c,len);
		NTT(d,len,-1);
		invv=qpow(len,mod-2);
		for(int i=0;i<len;i++){
			d[i]=d[i]*invv%mod;
		}
		CLR(d,len>>1);
		NTT(d,len,1);
		CROSS(d,c,len);
		NTT(d,len,-1);
		for(int i=len>>1;i<len;i++){
			b[i]=mod-d[i]*invv%mod;
		}
	}
	for(int i=0;i<lim;i++){
		b[i]%=mod;
	}
	CLR(b+n,lim-n);
	CLR(c,lim);
	CLR(d,lim);
}
int BSGS(int b,int n,int mod){
	int t=sqrt(mod)+1,now=1;
	unordered_map<int,int>mapp;
	for(int bb=0;bb<=t-1;bb++){
		mapp[1ll*now*n%mod]=bb;
		now=1ll*now*b%mod;
	}
	b=now;
	now=1;
	for(int aa=1;aa<=t;aa++){
		now=1ll*now*b%mod;
		if(mapp.count(now)){
			return aa*t-mapp[now];
		}
	}
	return -1;
}
void SQRT(ull *a,ull *b,int n){
	int lim=1,l=0;
	static ull c[N],d[N];
	b[0]=qpow(g,BSGS(g,a[0],mod)/2);
	b[0]=min(b[0],mod-b[0]);
	while(lim<n){
		lim<<=1;
		l++;
	}
	for(int len=2;len<=lim;len<<=1){
		CPY(c,b,len);
		INV(c,d,len);
		CPY(c,a,len);
		MUL(c,d,len<<1);
		ADD(b+(len>>1),c+(len>>1),len>>1);
		for(int i=len>>1;i<len;i++){
			b[i]=b[i]*inv2%mod;
		}
	}
	CLR(b+n,lim-n);
	CLR(c,lim);
}
void DIV(ull *a,ull *b,int n,int m){
	static ull c[N],d[N];
	REV(a,n);
	REV(b,m);
	CPY(c,b,n-m+1);
	INV(c,d,n-m+1);
	CPY(c,a,n-m+1);
	MUL(c,d,(n-m+1)<<1);
	CLR(c+n-m+1,n-m+1);
	REV(c,n-m+1);
	CPY(d,c,n-m+1);
	REV(a,n);
	REV(b,m);
	MUL(c,b,n<<1);
	CLR(c+n,n);
	DEC(a,c,n);
	CPY(b,a,m-1);
	CPY(a,d,n-m+1);
	CLR(c,n);
	CLR(d,n-m+1);
}
void LN(ull *a,ull *b,int n){
	static ull c[N];
	CPY(b,a,n);
	DRV(b,n);
	INV(a,c,n);
	MUL(b,c,n<<1);
	CLR(b+n,n);
	ITG(b,n);
}
void EXP(ull *a,ull *b,int n){
	int lim=1;
	static ull c[N],d[N];
	b[0]=1;
	while(lim<n){
		lim<<=1;
	}
	for(int len=2;len<=lim;len<<=1){
		CPY(c,b,len);
		CLR(d,len);
		LN(c,d,len);
		CLR(c,len);
		c[0]=1;
		DEC(c,d,len);
		ADD(c,a,len);
		MUL(b,c,len<<1);
		CLR(b+len,len);
		CLR(c+len,len);
	}
	CLR(b+n,lim-n);
	CLR(d,lim);
}
void POW(ull *a,int n,int k){
	static ull b[N];
	LN(a,b,n);
	for(int i=0;i<=n-1;i++){
		b[i]=b[i]*k%mod;
	}
	CLR(a,n);
	EXP(b,a,n);
	CLR(b,n);
}
void SIN(ull *a,ull *b,int n){
	int ii;
	static ull c[N],d[N]; 
	CPY(c,a,n);
	ii=qpow(g,BSGS(g,mod-1,mod)/2);
	for(int i=0;i<=n-1;i++){
		c[i]=c[i]*ii%mod;
	}
	EXP(c,b,n);
	CPY(d,b,n);
	CLR(c,n);
	INV(d,c,n);
	DEC(b,c,n);
	ii=qpow(ii,mod-2);
	for(int i=0;i<=n-1;i++){
		b[i]=b[i]*inv2%mod*ii%mod;
	}
}
void COS(ull *a,ull *b,int n){
	int ii;
	static ull c[N],d[N];
	CPY(c,a,n);
	ii=qpow(g,BSGS(g,mod-1,mod)/2);
	for(int i=0;i<=n-1;i++){
		c[i]=c[i]*ii%mod;
	}
	EXP(c,b,n);
	CPY(d,b,n);
	CLR(c,n);
	INV(d,c,n);
	ADD(b,c,n);
	for(int i=0;i<=n-1;i++){
		b[i]=b[i]*inv2%mod;
	}
}
void ARCSIN(ull *a,ull *b,int n){
	static ull c[N],d[N];
	CPY(b,a,n);
	DRV(b,n);
	CPY(c,a,n);
	MUL(c,c,n<<1);
	CLR(c+n,n);
	d[0]=1;
	DEC(d,c,n);
	CLR(c,n);
	SQRT(d,c,n);
	CLR(d,n);
	INV(c,d,n);
	MUL(b,d,n<<1);
	CLR(b+n,n);
	ITG(b,n);
	CLR(c,n<<1);
	CLR(d,n);
}
void ARCTAN(ull *a,ull *b,int n){
	static ull c[N],d[N];
	CPY(b,a,n);
	DRV(b,n);
	CPY(c,a,n);
	MUL(c,c,n<<1);
	CLR(c+n,n);
	d[0]=1;
	ADD(d,c,n);
	CLR(c,n);
	INV(d,c,n);
	MUL(b,c,n<<1);
	CLR(b+n,n);
	ITG(b,n);
	CLR(c,n<<1);
	CLR(d,n);
}
void EVALUATION(ull *a,ull *b,int n){
	static ull c[N],d[N],*q[N];
	function<void(ull *a,int,int,int)>init=[&](ull *a,int l,int r,int rt){
		int mid=(l+r)>>1;
		ull *tmpa=new ull[(r-l+3)<<1](),*tmpb=new ull[(r-l+3)<<1]();
		q[rt]=new ull[r-l+2];
		if(l==r){
			q[rt][0]=1;
			q[rt][1]=mod-a[l];
			delete[] tmpa;
			delete[] tmpb;
			return;
		}
		init(a,l,mid,rt<<1);
		init(a,mid+1,r,rt<<1|1);
		CPY(tmpa,q[rt<<1],mid-l+2);
		CPY(tmpb,q[rt<<1|1],r-mid+1);
		MUL(tmpa,tmpb,r-l+3);
		CPY(q[rt],tmpa,r-l+2);
		delete[] tmpa;
		delete[] tmpb;
	};
	function<void(ull*,ull*,int,int,int)>calc=[&](ull *f,ull *ans,int l,int r,int rt){
		int mid=(l+r)>>1;
		ull *a=new ull[(r-l+2)*3](),*b=new ull[(r-l+2)*3]();
		if(l==r){
			ans[l]=f[0];
			delete[] a;
			delete[] b;
			return;
		}
		CPY(a,f,r-l+1);
		CPY(b,q[rt<<1|1],r-mid+1);
		MULT(a,b,r-l+1,r-mid+1);
		calc(a,ans,l,mid,rt<<1);
		CPY(a,f,r-l+1);
		CPY(b,q[rt<<1],mid-l+2);
		MULT(a,b,r-l+1,mid-l+2);
		calc(a,ans,mid+1,r,rt<<1|1);
		delete[] a;
		delete[] b;
	};
	init(b,0,n-1,1);
	CPY(c,q[1],n);
	INV(c,d,n);
	MULT(a,d,n,n);
	calc(a,b,0,n-1,1);
}
void INTERPOLATION(ull *a,ull *b,int n){
	static ull c[N],d[N],*q[N],*ans[N];
	function<void(ull *a,int,int,int)>init=[&](ull *a,int l,int r,int rt){
		int mid=(l+r)>>1;
		ull *tmpa=new ull[(r-l+2)<<1](),*tmpb=new ull[(r-l+2)<<1]();
		q[rt]=new ull[r-l+2];
		if(l==r){
			q[rt][0]=mod-a[l];
			q[rt][1]=1;
			delete[] tmpa;
			delete[] tmpb;
			return;
		}
		init(a,l,mid,rt<<1);
		init(a,mid+1,r,rt<<1|1);
		CPY(tmpa,q[rt<<1],mid-l+2);
		CPY(tmpb,q[rt<<1|1],r-mid+1);
		MUL(tmpa,tmpb,r-l+2);
		CPY(q[rt],tmpa,r-l+2);
		delete[] tmpa;
		delete[] tmpb;
	};
	function<void(int,int,int)>calc=[&](int l,int r,int rt){
		int mid=(l+r)>>1;
		ans[rt]=new ull[r-l+1];
		if(l==r){
			ans[rt][0]=1ll*b[l]*qpow(d[l],mod-2)%mod;
			return;
		}
		calc(l,mid,rt<<1);
		calc(mid+1,r,rt<<1|1);
		ull *a=new ull[(r-l+1)<<1](),*b=new ull[(r-l+1)<<1]();
		CPY(a,ans[rt<<1],mid-l+1);
		CPY(b,q[rt<<1|1],r-mid+1);
		MUL(a,b,r-l+1);
		CPY(ans[rt],a,r-l+1);
		CLR(a,r-l+1);
		CPY(a,ans[rt<<1|1],r-mid);
		CPY(b,q[rt<<1],mid-l+2);
		MUL(a,b,r-l+1);
		ADD(ans[rt],a,r-l+1);
		delete[] a;
		delete[] b;
	};
	init(a,1,n,1);
	CPY(c,q[1],n+1);
	DRV(c,n+1);
	CPY(d,a+1,n);
	EVALUATION(c,d,n);
	for(int i=n;i>=1;i--){
		d[i]=d[i-1];
	}
	calc(1,n,1);
	CPY(b,ans[1],n);
}
void MOV(ull *a,int n,int m){
	int pro=1;
	static ull b[N];
	static int c[N];
	for(int i=0;i<=n-1;i++){
		a[i]=a[i]*ifac[i]%mod*ifac[n-1-i]%mod;
		if((n-1-i)%2){
			a[i]=(mod-a[i])%mod;
		}
	}
	for(int i=0;i<=2*(n-1);i++){
		b[i]=c[i]=qpow(m-(n-1)+i,mod-2);
	}
	MUL(a,b,n<<1);
	for(int i=m;i>=m-(n-1);i--){
		pro=1ll*pro*i%mod;
	}
	for(int i=0;i<=n-1;i++){
		a[i]=a[i+n-1]*pro%mod;
		pro=1ll*pro*c[i]%mod*(m+i+1)%mod;
	}
	CLR(a+n,n);
}
void calc(int l,int r,int rt){
	int mid=(l+r)>>1;
	ull *tmpa=new ull[(r-l+2)<<1](),*tmpb=new ull[(r-l+2)<<1]();
	d[rt]=new ull[r-l+2];
	if(l==r){
		d[rt][0]=1;
		d[rt][1]=mod-p[l];
		delete[] tmpa;
		delete[] tmpb;
		return;
	}
	calc(l,mid,rt<<1);
	calc(mid+1,r,rt<<1|1);
	CPY(tmpa,d[rt<<1],mid-l+2);
	CPY(tmpb,d[rt<<1|1],r-mid+1);
	MUL(tmpa,tmpb,r-l+2);
	CPY(d[rt],tmpa,r-l+2);
	delete[] tmpa;
	delete[] tmpb;
	delete[] d[rt<<1];
	delete[] d[rt<<1|1];
}
int main(){
	int n,m,ans=1;
	scanf("%d%d",&n,&m);
	fac[0]=inv[1]=1;
	for(int i=1;i<=n;i++){
		scanf("%d",&p[i]);
		fac[i]=1ll*fac[i-1]*i%mod;
		ans=1ll*ans*p[i]%mod;
	}
	ifac[n]=qpow(fac[n],mod-2);
	for(int i=n-1;i>=0;i--){
		ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
	}
	for(int i=2;i<=n;i++){
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	}
	ans=1ll*ans*fac[n-2]%mod;
	for(int i=0;i<=n-1;i++){
		a[i]=1ll*ifac[i]*qpow(i+1,m)%mod;
		b[i]=1ll*ifac[i]*qpow(i+1,2*m)%mod;
	}
	INV(a,c,n);
	MUL(b,c,n<<1);
	CLR(b+n,n);
	LN(a,c,n);
	CLR(a,n);
	calc(1,n,1);
	CPY(y,d[1],n+1);
	CPY(a,y,n+1);
	DRV(a,n+1);
	for(int i=n;i>=1;i--){
		a[i]=a[i-1];
	}
	a[0]=0;
	INV(y,x,n+1);
	MUL(a,x,(n+1)<<1);
	CLR(a+n+1,n+1);
	CLR(y,n+1);
	y[0]=n;
	DEC(y,a,n+1);
	CROSS(b,y,n);
	CROSS(c,y,n);
	CLR(a,n+1);
	EXP(c,a,n);
	MUL(a,b,n<<1);
	CLR(a+n,n);
	printf("%lld",1ll*a[n-2]*ans%mod);
}