Description：

给出标号 $1$ 到 $N$ 的点以及某些点最终的度数，允许在任意两点间连线，问可产生多少棵度数满足要求的树。

$1\leqslant n\leqslant 10^3$

Solution：

从 $prufer$ 序的角度思考，一个在树中度数为 $d[i]$ 的点在 $prufer$ 序中出现了 $d[i]-1$ 次，也就是说应该在 $prufer$ 序中选出 $d[i]-1$ 个位置放 $i$ ，由组合数得方案数为： $$ \frac{n-2}{\begin{align}\prod_{i=1}^n(d[i]-1)!\times (n-\sum_{i=1}^n(d[i]-1))!\end{align}} $$ 剩下的部分没有限制，可以随便放，于是方案数为： $$ (n-cnt)^{\begin{align}n-2-\sum_{i=1}^n(d[i]-1)\end{align}} $$ 两部分乘起来就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 1010

int d[MAXN];

int cnt = 0,sum = 0;

bool isprime[MAXN];

int prime[MAXN],tot = 0;

int mindiv[MAXN];

int w[MAXN];

void mul(int k)

{

	while(k != 1)

	{

		++w[mindiv[k]];

		k /= mindiv[k];

	}

	return;

}

void div(int k)

{

	while(k != 1)

	{

		--w[mindiv[k]];

		k /= mindiv[k];

	}

	return;

}

struct bigint

{

	int m[100000],l;

	bigint(){memset(m,0,sizeof(m));l = 0;}

	friend bigint operator * (bigint a,int b)

	{

		for(int i = 1;i <= a.l;++i)a.m[i] = a.m[i] * b;

		for(int i = 1;i <= a.l;++i)

		{

			a.m[i + 1] += a.m[i] / 10;

			a.m[i] = a.m[i] % 10;

		}

		while(a.m[a.l + 1] != 0)

		{

			++a.l;

			a.m[a.l + 1] += a.m[a.l] / 10;

			a.m[a.l] = a.m[a.l] % 10;

		}

		return a;

	}

}ans;

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&d[i]);

	for(int i = 1;i <= n;++i)

	{

		if(d[i] != -1)

		{

			++cnt;

			sum += d[i] - 1;

		}

	}

	for(int i = 2;i <= n;++i)isprime[i] = true;

	for(int i = 2;i <= n;++i)

	{

		if(isprime[i])

		{

			prime[++tot] = i;

			mindiv[i] = i;

		}

		for(int j = 1;j <= tot && i * prime[j] <= n;++j)

		{

			isprime[i * prime[j]] = false;

			mindiv[i * prime[j]] = prime[j];

			if(i % prime[j] == 0)break;

		}

	}

	for(int i = 1;i <= n - 2;++i)mul(i);

	for(int k = 1;k <= n;++k)if(d[k] != -1)

		for(int i = 1;i <= d[k] - 1;++i)div(i);

	for(int i = 1;i <= n - sum - 2;++i)div(i);

	for(int i = 1;i <= n - sum - 2;++i)mul(n - cnt);

	ans.l = 1;ans.m[1] = 1;

	for(int i = 1;i <= tot;++i)

	{

		for(int j = 1;j <= w[prime[i]];++j)

		{

			ans = ans * prime[i];

		}

	}

	for(int i = ans.l;i >= 1;--i)putchar(ans.m[i] + '0');

	puts("");

	return 0;

}