C++(clang++11) 解法, 执行用时: 34ms, 内存消耗: 528K, 提交时间: 2021-03-05 20:37:14

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL MAXN=1e3+10;
int n,a[MAXN],sum,prime[MAXN],tot,s[MAXN],k;
int ans[1000000];
bool book[MAXN];
int read(){int sss=0,fff=1;char ccc;ccc=getchar();while(ccc<'0'||ccc>'9'){if(ccc=='-')fff=-1;ccc=getchar();}while(ccc>='0'&&ccc<='9'){sss=sss*10+ccc-'0';ccc=getchar();}return sss*fff;}
void P(){
	for(int i=2;i<MAXN;i++){
		if(!book[i]) prime[++tot]=i;
		for(int j=1;j<=tot;j++){
			if(i*prime[j]>=MAXN) break;
			book[i*prime[j]]=true;
			if(i%prime[j]==0) break;}}}
void check(int x,int op){
	for(int i=1;i<=tot;i++)
		while(x%prime[i]==0)
			s[i]+=op,x/=prime[i];}
void mul(int x){
	for(int i=1;i<=ans[0];i++) ans[i]*=x;
	for(int i=1;i<=ans[0];i++)
		if(ans[i]>=10){
			ans[i+1]+=ans[i]/10;ans[i]%=10;
			if(i==ans[0]) ans[0]++;}}
int main(){
	P();n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		if(a[i]==0){printf("0\n");return 0;}
		if(a[i]!=-1) k++,sum+=a[i]-1;}
	if(sum>n-2){printf("0\n");return 0;}
	for(int i=1;i<=n-2;i++) check(i,1);
	for(int i=1;i<=n-2-sum;i++) check(n-k,1);
	for(int i=1;i<=n-2-sum;i++) check(i,-1);
	for(int i=1;i<=n;i++){
		if(a[i]==-1) continue;
		for(int j=2;j<a[i];j++) check(j,-1);}
	ans[0]=ans[1]=1;
	for(int i=1;i<=tot;i++)
		while(s[i])
			mul(prime[i]),s[i]--;
	for(int i=ans[0];i>=1;i--)
		printf("%d",ans[i]);
	return 0;}

Python3(3.5.2) 解法, 执行用时: 37ms, 内存消耗: 3924K, 提交时间: 2020-01-26 16:27:50

maxn = 1010
n = int(input())
deg = []
free = 0
for i in range(n):
    d = int(input())
    if d==-1: free+=1
    else: deg.append(d-1)
fact = []
for i in range(maxn):
    if i==0: fact.append(1)
    else: fact.append(fact[-1]*i)
tot = sum(deg)
ans = fact[tot]
for x in deg: ans //= fact[x]
ans *= fact[n-2]//fact[tot]//fact[n-2-tot]
for i in range(n-2-tot):
    ans *= free
print(ans)