题目链接

题面:

题解:
设有k个点已知度数,sum of (di - 1) = s
那么对于这些点有 ans = s!/((d1 - 1)! * (d2 - 1)! * … * (dk - 1) !)
这s个数在n-2个数中任选 C(n-2,s) * ans
剩下n-2-s个位置,剩下n-k个点 C(n-2,s) * ans * (n-k)n-2-s

代码:

def main():
    fac=[0 for i in range(1100)]
    a=[0 for i in range(1100)]
    fac[0]=1
    for i in range(1,1005):
        fac[i]=fac[i-1]*i

    k=0
    s=0
    n=int(input())
    for i in range(1,n+1):
        a[i]=int(input())
        if a[i]!=-1:
            k+=1
            s+=a[i]-1

    if n==1:
        if a[1]==0 or a[1]==-1:
            print(1)
        else:
            print(0)
        return
    
    if s>n-2:
        print(0)
        return 

    
    ans=fac[n-2]//fac[s]//fac[n-2-s]*fac[s]*((n-k)**(n-2-s))
    for i in range(1,n+1):
        if a[i]==0:
            print(0)
            return
        if a[i]==-1:
            continue
        ans=ans//fac[a[i]-1]
        
    print(ans)

main()