题解 P2624 【[HNOI2008]明明的烦恼】

2019-01-07 14:54:44


orz chen_zhe


前置知识

prufer序列

这篇blog讲的很好qwq

正解

设度数有限制的点的个数是 $cnt$ ,度数为 $d[i]$ ,再记一个 $\large sum=\sum\limits_{i=1}^{cnt}(d[i]-1)$ 。

不同排列的个数为 $\large C_{n-2}^{sum}\times \frac{sum!}{\prod\limits_{i=1}^{cnt}(d[i]-1)!}$

剩下还有 $n-2-sum$ 个位置可以随便放 $n-cnt$ 个点。

那么总方案数是 $\large C_{n-2}^{sum}\times \frac{sum!}{\prod\limits_{i=1}^{cnt}(d[i]-1)!}\times(n-cnt)^{n-2-sum}$ 。

化简,得到 $\large\frac{(n-2)!}{(n-2-sum)!\times\prod\limits_{i=1}^{cnt}(d[i]-1)!}\times(n-cnt)^{n-2-sum}$ 。

显然需要高精度。可以质因数分解来避免高精度除法。

代码见blog