题解 P5400 【[CTS2019]随机立方体】

· · 题解

前置知识

二项式反演，树的拓扑序

这里提下树的拓扑序

考虑这样一个问题：对于一颗 n 个点的有根有标号的叶向树，它有多少个不同的拓扑序呢？

记节点 i 的子树大小为 siz_i

考虑一个排列为树的合法拓扑序当且仅当对于所有 i，i 子树中的所有数出现位置在 i 之后

对于子树 i，我们将排列中属于子树 i 的 siz_i 个位置拿出来，i 有 \frac 1 {siz_i} 的概率处于第一个位置，显然子树之间独立

故有 n!\prod_{i=1}^n\frac 1 {siz_i}

\texttt{Solution}

不妨设 n\leq m\leq l

回到此题，我们对“恰好”非常敏感，将它二项式反演掉

记 f_i 表示有恰好 i 个极大点的概率，f_k 即为所求

记 g_i 表示有至少 i 个极大点的概率

g_k=\sum_{i=k}^n\tbinom i kf_i\iff f_k=\sum_{i=k}^n(-1)^{i-k}\tbinom i kg_i

考虑计算 g_i

我们首先有顺序的选出 i 个极大点，显然，这些点的三维坐标分别互不相同

即 n^{\underline i}m^{\underline i}l^{\underline i}

不妨设选出来的顺序是其填数从小到大的顺序

从小到大考虑极大点对其它点的限制，我们发现其形成了一个树形结构

这里给出一个二维情形的示意图

黑色编号代表关键点的大小顺序

1号点需大于黑色十字架上的其他点，我们将这些点的父亲定为1号点

2号点需大于蓝色十字架的部分与1号点，我们把1号点的父亲定为2号点，把蓝色十字架上的非黑色十字架部分的父亲定为2号点

这棵树里一共有 (n-i)(m-i)(l-i) 个点，容易发现给这些点赋权就是树的拓扑序问题

我们发现树中子树大小可能超过2的只有 i 个极大点

方案数为 (nml)!\prod_{j=1}^i\frac 1 {(n-j)(m-j)(l-j)}

概率去掉 (nml)! 即可

我们得到了 g_i=n^{\underline i}m^{\underline i}l^{\underline i}\prod_{j=1}^i\frac 1 {(n-j)(m-j)(l-j)}

套回二项式反演的式子可以在 O(n) 的时间内解决此问题

注意需要在线性时间内跑出 \prod 里面的逆元

代码