随机立方体

题意

给定一个 $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)$计算答案了。

方法 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$,我们所用到的组合数是完全不同的,因此每次必须重新计算。这个算法已经没有了优化的余地。

方法 2:直接计算概率

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

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

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

而 $S_i$实际上就是去除了前 $i$个黑球和至于前 $i$个黑球中的某些黑球相邻的球之后球总数,实际上就是 $(n-i)(m-i)(l-i)$。

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

注意到容斥后的式子为:
$$
\sum_{i=k}^{n}(-1)^k\binom{i}{k}\binom{n}{k}\binom{m}{k}\binom{l}{k}(k!)^3\prod_{j=1}^{i}\frac{1}{(n-j)(m-j)(l-j)}
$$
后面的那个累乘在每次计算时都会重复计算,因此只需要 $O(n)$的时间,我们就可以对 $\forall i$进行预处理,从而在统计时 $O(1)$访问。

实现技巧

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

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

分类: 文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注