C++14(g++5.4) 解法, 执行用时: 188ms, 内存消耗: 12896K, 提交时间: 2018-07-20 19:42:23

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

typedef long long s64;
#define rep(i,l,r) for(int i=l;i<=r;++i)
const int D=998244353;
s64 mi(s64 x,int y=D-2)
{
	s64 ans=1;
	while(y)
	{
		if(y&1)ans=ans*x%D;
		x=x*x%D;y>>=1;
	}
	return ans;
}
namespace NTT
{
const int N=1<<17;
s64 a[N],b[N],w[N];
int rev[N];
void ntt(s64 a[],int n,int flag)
{
	rep(i,1,n-1)rev[i]=rev[i/2]/2+i%2*n/2;
	rep(i,1,n-1)
	if(i<rev[i])swap(a[i],a[rev[i]]);
	for(int i=1;i<n;i*=2)
	{
		int nn=i*2;
		s64 wn=mi(3,D-1+(D-1)/nn*flag);
		w[0]=1;
		rep(k,1,i-1)w[k]=w[k-1]*wn%D;
		for(int j=0;j<n;j+=nn)
		{
			s64 *a1=a+j,*a2=a1+i;
			rep(k,0,i-1)
			{
				s64 x=a1[k],y=a2[k]*w[k]%D;
				a1[k]=(x+y)%D;
				a2[k]=(x-y)%D;
			}
		}
	}
	if(flag==-1)
	{
		s64 niv_n=mi(n);
		rep(i,0,n-1)a[i]=a[i]*niv_n%D;
	}
}
void mul(int n0)
{
	int n=1;
	while(n<=n0)n*=2;
	rep(i,n0+1,n-1)a[i]=b[i]=0;
	ntt(a,n,1);ntt(b,n,1);
	rep(i,0,n-1)a[i]=a[i]*b[i]%D;
	ntt(a,n,-1);
}
};
typedef pair<s64*,int> Poly;
const int N=1e5+5;
int a[N];
s64 jie[N];
s64 C(int n,int m)
{
	return jie[n]*mi(jie[m]*jie[n-m]%D)%D;
}
Poly solve(int l,int r)
{
	if(l==r)
	{
		s64 *f=new s64 [a[l]+1];
		f[0]=0;
		rep(i,1,a[l])f[i]=C(a[l],i);
		return Poly(f,a[l]);
	}
	int mid=(l+r)/2;
	Poly fl=solve(l,mid),fr=solve(mid+1,r);
	int n=fl.second+fr.second;
	rep(i,0,n)NTT::a[i]=NTT::b[i]=0;
	rep(i,0,fl.second)NTT::a[i]=fl.first[i];
	rep(i,0,fr.second)NTT::b[i]=fr.first[i];
	NTT::mul(n);
	s64 *f=new s64 [n+1];
	rep(i,0,n)f[i]=NTT::a[i];
	return Poly(f,n);
}

int main()
{
	//freopen("1.in","r",stdin);
	int n,m,k;
	cin>>n>>m>>k;
	rep(i,1,m)scanf("%d",a+i);
	jie[0]=1;
	rep(i,1,n)jie[i]=jie[i-1]*i%D;
	Poly f=solve(1,m);
	cout<<(f.first[k]+D)%D;
}

C++11(clang++ 3.9) 解法, 执行用时: 152ms, 内存消耗: 2792K, 提交时间: 2018-07-24 14:59:46

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 100010
#define Mod 998244353
#define LL long long
int a[N];
LL s1[N],s2[N],s[N];
LL find(LL x,LL y)
{
    LL ans=1;
    x=x%Mod;
    while(y)
    {
        if(y%2)
            ans=ans*x%Mod;
        x=x*x%Mod;
        y=y/2;
    }
    return ans;
}
LL C(int x,int y)
{
    if(x<y)
        return 0;
    return s1[x]*s2[y]%Mod*s2[x-y]%Mod;
}
int main()
{
    int n,m,k,i,j,t,d;
    LL ans;
    scanf("%d%d%d",&n,&m,&k);
    for(i=1;i<=m;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+m+1);
    s1[0]=1;
    for(i=1;i<=n;i++)
        s1[i]=s1[i-1]*i%Mod;
    s2[n]=find(s1[n],Mod-2);
    for(i=n;i>=1;i--)
        s2[i-1]=s2[i]*i%Mod;
    d=0;
    s[0]=1;
    for(i=1;i<=m;i++)
    {
        for(j=d+a[i];j>=a[i];j--)
            s[j]=(s[j]-s[j-a[i]])%Mod;
        d=d+a[i];
    }
    ans=0;
    for(i=0;i<=d;i++)
        ans=(ans+s[i]*C(d-i,k)%Mod)%Mod;
    ans=(ans+Mod)%Mod;
    printf("%lld\n",ans);
    return 0;
}