随机立方体

题意

给定一个 $n\times m\times l$的立方体，在里面随机填入 $1\dots nml$的排列，求恰好有 $k$个极大值的概率。极大值定义为比所有与它有至少一维坐标相同的所有数都大的数。$n,m,l\leq 5\times 10^6$

分析

先将条件放宽，最后用容斥计算答案，总会让问题变简单。

我们求出” 至少有 $k$个极大值” 的概率，最后用二项式反演就可以求出 “恰好有 $k$个极大值” 的概率，而且计算相对更为容易，因为条件更少，我们只需要保证其它的数比我们钦定的 $k$个极大值小就可以了。但是，问题也有一个，就是不使用容斥，我们可以去 $O(n)$计算答案，但是使用了容斥，我们不得不算出 $\forall i\geq k$的答案，这意味着我们必须 $O(1)$计算答案了。

计算方案数

我们先尝试继续推下去，为了计算概率，我们可以先统计出合法情况的总数。

随便钦定 $k​$个极大值的方案数是 $\binom{n}{k}\binom{m}{k}\binom{l}{k}(k!)^3​$，接下来，我们只需要确保这些极大值和与它们相邻 (即有一维坐标相同) 的数之间的大小关系即可，不与任何钦定的数相邻的数随便填什么，不会使任何一个已经被钦定的数变得不再是最大值，因此它们随便乱填即可，我们不去考虑它们。

假设这 $k$个极大值分别为 $x_1<x_2<\dots <x_k$，我们可以把它们想象成一列黑色的球，与它们相邻 (即在立方体中共面) 的数都是一些白球，需要插空放在黑球之间。

所有合法情况的总数实际上就是这些白色球的摆放方式之和。只与 $x_i$相邻的白球只能摆在 $x_i$前面，与多个 $x$相邻的白球就得摆在最小的那个 $x$的前面。因此，我们从小往大用组合数统计白色球的摆放方式就可以 $O(n)$计算出答案了。至于每一种白球有多少个，这个经过不太复杂的数学计算是可以得出的：

• 只与 $x_i$相邻的数的数量为 $(nm+nl+ml)-2(n+m+l)k+(n+m+l)-3k+3k^2$
• 同时与 $x_i,x_j$相邻的球的数量为 $2(n+m+l)-12$
• 同时与 $x_i,x_j,x_l$相邻的球的数量为 $6$
• 不与任何 $x​$相邻的球的个数为 $(n-k)(m-k)(l-k)​$

这时，整个算法的时间复杂度就是 $O(n^2)$，可以获得 $50$分。

由于这样统计时，对于不同的 $k$，我们所用到的组合数是完全不同的，因此每次必须重新计算。这个算法已经没有了优化的余地。

直接计算概率

我们知道，互相独立的概率是可以直接乘起来，得到两件事情同时发生的概率的。

我们知道，有一些白球和某些黑球之间有先后顺序的限制，黑球之间也被钦定了先后顺序。只有剩下的没有与任何黑球相邻的白球，我们先不去考虑它们。

假设所有球共有 $S$个，那么我们钦定的最大的黑球出现在序列最右边的概率就是 $\frac{1}{S}$。这个概率已经隐含了 “剩下的所有球” 都在它左边这一条件了，因此，我们将所有 “只与该黑球相邻” 的白球和这个黑球删掉，我们只需要让剩下的球满足先后顺序即可。不难发现这是一个递归关系，一直递归下去，球的总数不断减少，每次，我们将答案累乘 $\frac{1}{S_i}$。我们只需要知道每个 $S$分别是多少，就可以求出答案了。

而 $S_i$实际上就是去除掉前 $i-1$个黑球以及只与它们中的若干个相邻的白球之后，剩下的球的个数。$S_i=nml-T$其中 $T$表示所有被去掉的球。而 $T$很好计算，任选三个没有被覆盖的坐标组成的点都构成一个没有被覆盖的球。

将 $S_i$直接代入容斥式得：

$$
\sum_{i=k}^{n}(-1)^{i-k}\binom{i}{k}\binom{n}{i}\binom{m}{i}\binom{l}{i}(i!)^3\prod_{j=1}^{i}\frac{1}{nml-(n-j)(m-j)(l-j)}
$$

现在，我们又可以 $O(n)$对于 $\forall i>k$计算答案了。实际上，这个算法还可以优化。

后面的那个累乘在每次计算时都会重复计算，因此只需要 $O(n)$的时间，我们就可以对 $\forall i$进行预处理，从而在统计时 $O(1)$访问。

实现技巧

为了快速处理 $\prod_{j=1}^{i}\frac{1}{nml-(n-j)(m-j)(l-j)}$，我们需要利用到类似阶乘求逆元的方法，才能达到 $O(n)$

代码处处有，随便哪个 OJ 都可以看到。