BZOJ 1211 [HNOI2004] 树的计数

发布于 2017-06-14  71 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1211

题意:对于 n 阶完全图,求在限定每个点度数的情况下生成树的个数...


考虑生成 prufer 序列的过程,记点 i 度数为\(d_i\),显然会在序列中出现\(d_i-1\) 次,那么就是元素可重的排列计数问题了...

重述题意:对于 n-2 个元素,其中第 i 种元素有\(d_i-1\) 个,求有多少种不同的排列方式...

考虑 n-2 个元素的全排列为\((n-2)!\)

单独考虑第 i 种元素,在确定其他元素排布后,对于自身的位置互换都是同一种排列,有\((d_i-1)!\) 种排列方式在全排列中重复了,扩展到每一种元素,显然是按照乘法原理记录

所以$$ans=\frac{(n-2)!}{\prod_{i=1}^{n}(d_i-1)!}$$

运算过程会爆 long long 所以需要分解质因数后计算

但是蒟蒻博主想到了一个脑残的问题,如何保证分解质因数统计每个质因素的个数后不会出现负数呢,也就是说原式是否一定为整数。直觉上是显然的.... 怎么证明呢?

在吃黄焖鸡米饭的时候想明白了...

首先生成树的总度数一定为 2*(n-1),也就是说\(\sum_{i=1}^{n}d_i=2(n-1)\)

我们考虑对于质因子 k,在\($$ans=\frac{(n-2)!}{\prod_{i=1}^{n}(d_i-1)}$$\) 的分子中出现的次数小于在分母中出现的次数

在分子中显然出现\(q=\frac{(n-2)!}{k}\) 次,在分母中出现\(p=\sum_{i=1}^{n}\left \lfloor \frac{d_i-1}{k} \right \rfloor\) 次

考虑到下取整后答案一定不变或者变差,记\(p'=\sum_{i=1}^{n}\frac{d_i-1}{k}\leq p\)

\(p'=\frac{\sum_{i=1}^{n}(d_i-1)}{k}=\frac{2(n-1)-n}{k}=\frac{n-2}{k}\)

显然\(q\geq p\) 所以这么搞不会有问题...

大概只有我能想到这么愚蠢的问题还去证明了一遍的...


一个非常弱的准退役OIER