C++14(g++5.4) 解法, 执行用时: 114ms, 内存消耗: 6360K, 提交时间: 2018-06-08 09:07:07

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include <queue>
#include <vector>
#include <cmath>
#include <map>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lrt rt<<1
#define rrt rt<<1|1
using namespace std;
typedef long long LL;
const int maxn=900+5;
const LL mod=1e9+7;
LL c[maxn][maxn];
LL dp[35][905];
int a[35];
int main()
{
    for(int i=0;i<maxn;i++)
        c[i][0]=1;
    for(int i=1;i<maxn;i++)
        for(int j=1;j<=i;j++)
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        memset(dp,0,sizeof(dp));
        dp[1][a[1]-1]=1;
        int num=a[1];
        for(int i=2;i<=n;i++)
        {
            for(int j=0;j<num;j++)
                for(int k=1;k<=a[i];k++)
                    for(int q=0;q<=min(j,k);q++)
                        dp[i][j-q+a[i]-k]=(dp[i][j-q+a[i]-k]+(dp[i-1][j]*c[a[i]-1][k-1]%mod*c[j][q]%mod*c[num+1-j][k-q]%mod))%mod;
            num+=a[i];
         }
         printf("%lld\n",dp[n][0]);
     }
}

C++ 解法, 执行用时: 893ms, 内存消耗: 788K, 提交时间: 2022-04-17 09:46:25

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,f[31][1010],p=1e9+7,a[1010],sum[1010],jc[100010],ny[100010];
ll C(ll x,ll y){
	if(x<0||y<0||x<y)return 0;
	return jc[x]*ny[y]%p*ny[x-y]%p;
}
ll ksm(ll x,ll y){
	ll xlh=1;
	while(y){
		if(y&1)xlh=xlh*x%p;
		x=x*x%p;
		y/=2;
	}
	return xlh;
}
int main(){
	ll i,j,x,y,t1;
	jc[0]=ny[0]=1;
	for(i=1;i<=10000;i++)jc[i]=jc[i-1]*i%p,ny[i]=ksm(jc[i],p-2);
	scanf("%lld",&t1);
	while(t1--){
		scanf("%lld",&n);
		for(i=1;i<=n;i++){
			scanf("%lld",&a[i]);sum[i]=sum[i-1]+a[i];
		}
		for(i=1;i<=n;i++)
		 for(j=0;j<=sum[n];j++)f[i][j]=0;
		f[1][a[1]-1]=1;
		for(i=1;i<n;i++){
			for(j=0;j<=sum[i];j++)if(f[i][j]){
				for(x=1;x<=a[i+1];x++)
				 for(y=0;y<=min(x,j);y++){
				 	(f[i+1][j-y+a[i+1]-x]+=f[i][j]*C(sum[i]+1-j,x-y)%p*C(j,y)%p*C(a[i+1]-1,x-1)%p)%=p;
				 }
			}
		}
		printf("%lld\n",f[n][0]);
	}
}