【BZOJ1005】【HNOI2008】明明的烦恼

学一下Prufer序列。。

对于一棵带编号的无根树而言,它的Prufer序列的构造方法为:每次找到度数为1的编号最小的点,删掉该点并将与它相连的那个点加入Prufer序列,直至只剩两个点为止。

将Prufer序列转化为一棵带编号的无根树的方法为:创建一个含有[1,n]的新序列b,每次找到b中最小的未在Prufer序列中出现的数,将该点与Prufer序列中的第一个数连边,然后删去这两个数。最后将b中剩下两个数连边。

可以发现几个性质:

  1. 每个Prufer序列唯一对应一棵带编号的无根树。
  2. 在Prufer序列中,一个数的出现次数为该点的度数-1。

第一个性质让它非常适合处理组合数学中树的统计问题,而第二个性质就是这道题要用到的了。。

题意给定了每个点的度数,也就是告诉了每个数在Prufer序列中的出现次数。

所以就可以随便组合乱搞了。。

令\(free\)为没有度数限制的点的个数,\(tot\)为已经定好的次数总和。

$$\begin{align}
ans&=\mathrm{C}_{n-2}^{tot}\times \mathrm{C}_{tot}^{d_1-1}\times \mathrm{C}_{tot-(d_1-1)}^{d_2}\times ···\times free^{n-2-tot}\\
&=\frac{(n-2)!tot!(tot-(d_1-1))!…}{tot!(n-2-tot)!(d_1-1)!(n-2-(d_1-1))!···}\times free^{n-2-tot}\\
&=\frac{(n-2)!}{(n-2-tot)!(d_1-1)!(d_2-1)!···}\times free^{n-2-tot}\\
\end{align}$$

!似乎可以用一些奇技淫巧

这道题非常蛋疼的是要开高精度。。

说点什么

  Subscribe  
提醒