【CTS2019】随机立方体

题目

随便观察一下,不难发现如下的性质:

  1. 任意两个极大值点((x_1,y_1,z_1),(x_2,y_2,z_2))都存在(x_1 eq x_2,y_1 eq y_2,z_1 eq z_2),这是因为极大值点必须大于其所在平面上的任意数。

  2. 根据上面的性质不难发现极大值点的个数不会超过(min(n,m,l))

要求的是恰有(k)个极大值点的概率,如果有(ans)种方案满足要求,那么答案就是(frac{ans}{(nml)!})

这一看就不能直接做,考虑二项式反演,求一个(g_i)表示至少存在(i)个极大值点的方案数。那么显然有(ans=sum_{i=k}^{min(n,m,l)}(-1)^{i-k}inom{i}{k}g_i)

考虑(g_i)怎么求,首先我们得先选出(i)个三维坐标互不相同的点,之后会剩下((n-i)(m-i)(l-i))个点,这些点不和任何被钦定的极大值点在同一个平面内,所以没有限制,随便选出来就好了。这边的方案数就是(n^{underline i}m^{underline i}l^{underline i}(nml)^{underline {(n-i)(m-i)(l-i)}})

对于剩下的(nml-(n-i)(m-i)(l-i))个点我们要确定一个顺序,使得钦定的(i)个点都成为极大值点。

(varphi(i)=(n-i)(m-i)(l-i)),由于前面我们确定了点的顺序,考虑从大到小考虑每一个极大值点。我们发现当我们确定一个极大值点填什么的时候,会有一些点被解放出来,这些点就可以随便填了。不难发现这些点只和这个极大值点在同一个平面上,于是我们能确定这些点的个数。

存在(i-1)个极大值点的时候,有限制的点的个数是(nml-varphi(i-1));当极大值点变成(i)个的时候,有限制的点变成了(nml-varphi(i))个。不难发现这些新增加的点就是只被这个新加入的极大值点控制的点,这样的点的个数是(nml-varphi(i)-nml+varphi(i-1)=varphi(i-1)-varphi(i))个。我们确定好当前这个极大值的值后这些被控制的点就可以随便填了,于是方案数就是(A(nml-varphi(i)-1,varphi(i-1)-varphi(i)-1)=frac{(nml-varphi(i)-1)!}{(nml-varphi(i-1))!})

于是填(i)个极大值点的方案数就是(prod_{j=1}^ifrac{(nml-varphi(j)-1)!}{(nml-varphi(j-1))!}),经过一番约分可以发现其实就是((nml-varphi(i)-1)!prod_{j=1}^ifrac{1}{nml-varphi(j-1)})。不难发现((nml-varphi(i)-1)!)((nml)^{underline {varphi(i)}})很搭,乘在一起就是((nml)!(nml-varphi(i))!)

于是

[g_i=n^{underline i}m^{underline i}l^{underline i}(nml)^{underline {varphi(i)}}(nml)!prod_{j=1}^ifrac{1}{nml-varphi(j)} ]

容斥后还需要除一个((nml)!),于是直接在容斥的过程中将其除掉即可。

用一下线性求逆元的trick就可以做到(O(Tn))了。

代码

原文地址:https://www.cnblogs.com/asuldb/p/12939103.html