原问题等价于询问节点个数为 $ n $ 的完全二叉树形态的二叉堆的个数。

考虑递推,用 $ f(i) $ 表示 $ i $ 个节点时的答案。考虑除去此时的根节点外,根的左右子树大小分别为 $ l $ 和 $ r $ (可由完全二叉树这一性质计算得出)。此时根节点的编号肯定为 $ 1 $ ,而 $ f(l) $ 和 $ f(r) $ 分别是子树中的根节点编号为 $ 1 $ 的情况,若把编号分配,相当于求两个有序数列并成一个的方案数,即 $ C _ { l + r} ^ l $。得出:

$$ f(i) = f(l) \times f(r) \times C _ { l + r } ^ l $$

预处理阶乘递推即可。若 $ n > q $ 则需要卢卡斯定理简单处理。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×