C++11(clang++ 3.9) 解法, 执行用时: 278ms, 内存消耗: 7644K, 提交时间: 2018-03-09 19:25:50

#include <bits/stdc++.h>
using namespace std;

typedef long long  LL;
typedef pair <int,int>  PII;
const int N=50010,mo=998244353,g=3;
int n,s,a[N],fac[N],ifac[N],A[1<<17],B[1<<17],ans;
vector <int> V[N];
priority_queue <PII,vector <PII> ,greater <PII> > Q;

int qpow(int a,int b)
{
	int x=a;  a=1;
	while (b)
		{
			if (b&1)  a=1LL*a*x%mo;
			x=1LL*x*x%mo,b>>=1;
		}
	return a;
}

int C(int n,int m){return 1LL*fac[n]*ifac[m]%mo*ifac[n-m]%mo;}

void NTT(int *a,int n,int op)
{
	for (int i=1,j,x,t; i<n; i++)
		{
			for (x=i,j=0,t=1; t<n; j<<=1,j|=x&1,x>>=1,t<<=1);
			if (i<j)  swap(a[i],a[j]);
		}
	unsigned int w,W,u,v;
	for (int len=2; len<=n; len<<=1)
		{
			w=qpow(g,(mo-1)/len);
			if (op<0)  w=qpow(w,mo-2);
			for (int i=0; i<n; i+=len)
				{
					W=1;
					for (int j=0; j<(len>>1); j++)
						{
							u=a[i+j],v=1LL*a[i+j+(len>>1)]*W%mo,W=1LL*W*w%mo;
							a[i+j]=(u+v>=mo)?(u+v-mo):(u+v);
							a[i+j+(len>>1)]=(u>=v)?(u-v):(u-v+mo);
						}
				}
		}
	if (op<0)
		{
			int inv=qpow(n,mo-2);
			for (int i=0; i<n; i++)  a[i]=1LL*a[i]*inv%mo;
		}
}

void mul(int x,int y)
{
	int N=1,xs=a[x],ys=a[y];
	while (N<=xs+ys)  N<<=1;
	for (int i=xs; i; i--)  A[i]=V[x][i];
	for (int i=ys; i; i--)  B[i]=V[y][i];
	NTT(A,N,1),NTT(B,N,1);
	for (int i=0; i<N; i++)  A[i]=1LL*A[i]*B[i]%mo;
	NTT(A,N,-1);
	a[x]+=a[y],V[x].resize(a[x]+1);
	for (int i=a[x]; i>=0; i--)  V[x][i]=A[i];
	for (int i=0; i<N; i++)  A[i]=B[i]=0;
}

void work()
{
	scanf("%d",&n),s=ans=0;
	for (int i=1; i<=n; i++)  scanf("%d",&a[i]),s+=a[i];
	fac[0]=1;
	for (int i=1; i<=s; i++)  fac[i]=1LL*fac[i-1]*i%mo;
	ifac[s]=qpow(fac[s],mo-2);
	for (int i=s; i; i--)  ifac[i-1]=1LL*ifac[i]*i%mo;
	for (int i=1; i<=n; i++)
		{
			V[i].resize(a[i]+1),Q.push(make_pair(a[i],i));
			for (int j=1; j<=a[i]; j++)  V[i][j]=1LL*C(a[i]-1,j-1)*ifac[j]%mo;
		}
	for (int _=1,x,y; _<n; _++)
		{
			y=Q.top().second,Q.pop(),x=Q.top().second,Q.pop();
			mul(x,y),Q.push(make_pair(a[x],x));
		}
	for (int i=1,x=Q.top().second; i<=s; i+=2)  ans=(ans+1LL*V[x][i]*fac[i])%mo;
	Q.pop();
	printf("%d %d\n",(n==s?(n&1?1:0):499122177),ans);
}

int main()
{    work();
	return 0;
}