C++(g++ 7.5.0) 解法, 执行用时: 36ms, 内存消耗: 31896K, 提交时间: 2022-10-18 20:13:47

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;

ll C[2005][2005],f[2005];
int n,m;
int a[2005];

void getC()
{
    for (int i=0; i<=2000; ++i)
    {
        for (int j=0; j<=i; ++j)
        {
            if (j==0 || j==i) C[i][j]=1;
            else C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
        }
    }
}

int main()
{
    memset(C,0,sizeof(C));
    cin>>n>>m;
    for (int i=1; i<=m; ++i) cin>>a[i];
    getC();
    for (int i=0; i<n; ++i)
    {
        f[i]=C[n][i];
        ll sum=1;
        for (int j=1; j<=m; ++j) sum=(sum*C[a[j]+n-i-1][n-i-1])%mod;
        f[i]=f[i]*sum%mod;
    }
    ll ans=0;
    for (int i=0; i<n; ++i)
        if (i%2==0) ans=(ans+f[i])%mod;
        else ans=(ans-f[i]+mod)%mod;
    cout<<ans;
    return 0;
}

C++(clang++11) 解法, 执行用时: 18ms, 内存消耗: 14332K, 提交时间: 2020-10-29 15:08:44

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e3+5,mod=1e9+7;
int n,m,a[N],c[N][N],ans;
void add(int &x,int y){x=(x+y>=mod)?x+y-mod:x+y;}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)scanf("%d",&a[i]);
	for(int i=0;i<N;i++)c[i][0]=1;
	for(int i=1;i<N;i++)for(int j=1;j<=i;j++)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	for(int i=0,sgn=1,res;i<n;i++,sgn=-sgn){
		res=c[n][i];
		for(int j=1;j<=m;j++)res=(LL)res*c[a[j]+n-i-1][n-i-1]%mod;
		add(ans,(res*sgn+mod)%mod);
	}
	printf("%d\n",ans);
	return 0;
}