CSAcademy heap-count 题解

sh没想到这个 trick 还能见到第二遍。

从 AT_agc030_d 学到的。

首先对于堆的个数，我们可以转化成树的拓扑序计数。

首先自底向上 DP 难以避免平方的状态数，因此我们考虑自上而下 DP。

简而言之，考虑 表示已经放了前 个数，此时的轮廓线是 。转移考虑枚举下一个数进行转移。

然后你发现时空双飞。

不过转念一想，我们真的需要记录整个轮廓线吗？我们其实是想知道走了几步之后往我们的目标节点跨了一步。

然而如果我们需要干计数的话，我们必须要记录轮廓线。因为每个节点的后继状态并不相同。

举个例子，有些节点走一步可能会增加一个节点（因为有两个儿子），有的节点走一步可能不变（一个节点），而叶子可能减少 。

这很坏！

不过，从 AT_agc060_c 可以知道，此类情况的概率是容易计算的。

假设剩下子树 ， 子树内部的方案为 。

那么，总共的方案数是

假设你需要先走进 。那么此类的方案数是

其中 ，即多重集组合数。

然后你除以下，发现是 。

然后你直接 表示前 个走了到了 的 层祖先。最后树的拓扑序个数是好求的，乘上一个这个即可。

做完了。