C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 396K, 提交时间: 2022-08-19 20:57:01

#include<bits/stdc++.h>
using namespace std ;
const int N = 155 ;
#define ll long long
int n ;
int d[N] ;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a ; }
int main()
{
	cin>>n ; int sz=0 ;
	for(int i=1;i<=n;++i)
	{
		cin>>d[i],d[i]--,sz+=d[i] ;
		if(d[i]<0&&n>1) return cout<<0<<'\n',0 ;
	}
    //if(n==1) return cout<<(d[1]==0?1:0)<<'\n',0 ;
    if(sz!=n-2) return cout<<0<<'\n',0 ;
	ll t[N],s[N][N] ;
	for(int i=1;i<=sz;++i) t[i]=i ;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=d[i];j++)
			s[i][j]=j ;
	for(int i=1;i<=n;++i)
	{
		if(d[i]==0) continue ;
		for(int j=1;j<=d[i];j++)
			for(int k=1;k<=sz;++k)
			{
				ll d=gcd(s[i][j],t[k]) ;
				s[i][j]/=d ; t[k]/=d ;
			}
	}
	ll ans=1 ;
	for(int i=1;i<=sz;++i) ans*=t[i] ;
	cout<<ans<<'\n' ; 
	return 0 ;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 460K, 提交时间: 2022-03-16 16:45:52

/*
HNOI2004 树的计数 
*/
#include<bits/stdc++.h>
using namespace std;
const int Max_N=150;
int n,d[Max_N+5];
long long C[Max_N+5][Max_N+5];
int main(){
	scanf("%d",&n); int sumd=0; 
	for(int i=1;i<=n;i++) scanf("%d",&d[i]),sumd+=d[i];
	if(sumd!=2*(n-1)){ puts("0"); return 0; }
	if(n==1){ puts("1"); return 0; }
	C[0][0]=1;
	for(int i=1;i<=n;i++){
		C[i][0]=1;
		for(int j=1;j<=i;j++)
		 C[i][j]=(C[i-1][j]+C[i-1][j-1]);
	}
	long long ans=1; int sum=0;
	for(int i=1;i<=n;i++)
	 ans*=C[n-2-sum][d[i]-1],sum+=d[i]-1;
	printf("%lld\n",ans);
	return 0;
} 

Python3(3.5.2) 解法, 执行用时: 46ms, 内存消耗: 3352K, 提交时间: 2020-02-04 21:04:58

import math
n = int(input())
lis = [int(x) for x in input().split()]
if n==1:
    if lis[0]==0:
        print(1)
    else:
        print(0)
    exit(0)
tot = sum(lis) - n
if tot != n-2:
    print(0)
    exit(0)
ans = math.factorial(n-2)
for d in lis:
    if d<=0 or d>n-1:
        print(0)
        exit(0)
    ans //= math.factorial(d-1)
print(ans)