RainAir
My OI Blog
RainAir
「JZOJ6284」玩具

链接

题目描述

随机一棵以 $1$ 为根,且节点编号满足小根堆性质的树的期望最大深度。
$n \leq 200$

题解

这个题我考试的时候连 $n \leq 20$ 都不会..还是自己太菜了。

一开始的一个想法是记 $f_{i,j}$ 表示前 $i$ 个点深度为 $j$ 的树的个数,然后发现不太能转移需要记录最后一层的节点个数。。然后还要记录前面层的所以复杂度就炸了。
然后我们考虑放宽限制,对森林计数,并且我们不妨做一步容斥:设 $f_{i,j}$ 表示 $i$ 个节点,最大深度 $\leq j$ 的树的个数,$g_{i,j}$ 表示 $i$ 个节点,最大深度为 $j$ 的森林的个数。
我们首先预处理出 $dp_{i,j}$ 表示从 $i$ 个点中选出 $j$ 个点组成一棵树的概率,转移
$$dp_{i,j} = dp_{i-1,j-1} * \frac{j-1}{i} + dp_{i-1,j} * \frac{i-j}{i}$$
用 $g$ 转移 $f$ 的时候我们可以考虑变出一个根把这些树都接到根上,有 $f_{i,j} = g_{i-1,j-1}$
用 $f$ 转移 $g$ 其实是一个经典套路:我们枚举编号最小的点所在的树的大小,那么有转移
$$g_{i,j} = \sum_{k=1}^i f_{k,j} * dp_{i,k} * g_{i-k,j}$$
其中 $f_{k,j} * dp_{i,k}$ 是计算了拿出 $k$ 个点组成一棵树的概率,所以我们不需要关系组合计数那一堆东西了(有时候把概率引入到状态就是好用)
答案统计就不说了。

反思

对于树的计数:如果对度数进行限制就对 prufer 序列进行计数,对深度进行限制可以考虑利用森林辅助转移。
其实树是点的集合,森林是树的集合,如果我们固定 $j$,那么树的生成函数 $F$ 和森林的生成函数 $G$ 满足 $e^F = G$(虽然这个题目只能提高复杂度)
并且考试一定要把所有性质读完,要不然会导致漏掉性质把会做的题不会做
概率问题计数不可做可以考虑直接设概率为状态(就是不知道会不会有计数转概率最后再乘回去的)

题解

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/936
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「JZOJ6284」玩具
链接 题目描述 随机一棵以 $1$ 为根,且节点编号满足小根堆性质的树的期望最大深度。 $n \leq 200$ 题解 这个题我考试的时候连 $n \leq 20$ 都不会..还是自己太菜了。 一开始的一个…
扫描二维码继续阅读
2019-11-01
标签
近期评论