给出一棵树中所有节点的度数（ $-1$ 代表无限制），求可能的树的种类数。
$0<N\leq1000$
嘛，这是我少有的单独为一道题写的博客，这水题卡了我一晚上，不过不能否认，这道题对现在的我来说确实很有价值，本体需要先推公式，然后分解质因数搞高精。
我们考虑用 $pufer$ 编码来表示一棵树，根据 $pufer$ 编码的性质：
- 任何一棵无根树都可以表示为长度为 $n-2$ 的串；
- 一个点的度数是 $d$ ，则它会在串中出现 $d-1$ 次。
我们知道该已知度数的节点组成的串的总长度 $\displaystyle len=\sum_{i=1}^nd_i-1$ ，将长度为 $len$ 的串中的数插入到总的串中，方法有 $\binom{len}{n-2}$ 种，而长度为 $len$ 的串共有 $\displaystyle\binom{len}{d_1-1}\binom{len-(d_1-1)}{d_2-1}\dots\binom{d_n-1}{d_n-1}$ 种，再算上 $m$ 个无度数限制的节点的 $m^{n-2-len}$ 种，根据乘法原理：
$$
\begin{eqnarray}
ans&=&\binom{len}{n-2}\binom{len}{d_1-1}\binom{len-(d_1-1)}{d_2-1}\dots\binom{d_n-1}{d_n-1}m^{n-2-len}\
&=&\frac{(n-2)!}{(n-2-len)!len!}\cdot\frac{len!}{(d_1-1)!(len-d_1-1)!}\dots\frac{(d_n-1)!}{(d_n-1)!0!}\cdot m^{n-2-len}\
&=&\frac{(n-2)!\cdot m^{n-2-len}}{(n-2-len)!\prod_{i=1}^n(d_i-1)!}
\end{eqnarray}
$$
由于答案十分巨大，需要写高精，不过高精除比较恶心，所以我们考虑分解质因数。
1 | /************************************************************** |