本文主要是介绍CTS2019 / CTSC2019」随机立方体，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意
有一个 n × m × l n\times m\times l n×m×l的立方体，在其中填上 1 − n × m × l 1-n\times m\times l 1−n×m×l的数，求刚好有k个数满足：这个数大于与其至少有一维相同的所有数的概率。(有 T T T组数据)
范围
n,m,l<=5e6,k<=100，T<=10
题解
首先%一下神犇xjq
吐槽一下数据范围，为什么k要<=100啊，甚至%50的数据范围给了k=1，害我考场上一直往k=1上想，然后自闭了。。。
其实还是我太菜了，根本没有往容斥上想，（此处总结：计数类问题想不出来就往容斥想）。因为直接刚好有k个数满足肯定不好限制，故考虑至少有k个数满足（其实这不严格，应该说考虑重复下的概率，因为有重复，所以容斥时要乘组合数），于是强制让k个一定满足，其他的不考虑，开始大力写式子吧。
可这还是好难啊。。。于是先考虑至少一个的情况，考虑这一个有 n × m × l n\times m\times l n×m×l种位置，对于每种位置，考虑它满足条件的限制，即为与它至少有一维相同的数都比它小，那这样的概率要怎么算呢？考虑这其实就是它为一些数中的最大值，在没有其他限制下，概率自然就是1/集合大小，于是再乘 n × m × l n\times m\times l n×m×l的位置种数，即为至少有一个的概率。（当时听到这里有一个疑问：为什么概率可以大于1？因为这是假的啊，它多算了后面的对它的很多影响，这其中有很多重复的情况，所以容斥时才要乘上组合数）
那么考虑至少有k个，从大到小考虑（肯定要确定一个顺序嘛）。对于最大的那个，就按照至少有一个的计算，对于第i大的，它可以放的位置就是 ( n − i + 1 ) × ( m − i + 1 ) × ( l − i + 1 ) (n-i+1)\times (m-i+1)\times (l-i+1) (n−i+1)×(m−i+1)×(l−i+1)种，而它要满足的条件是大于所有比它小的限制，因为是并集，故考虑用总的减去没有限制的交集，集合大小为 n × m × l − ( n − ( k − i + 1 ) ) × ( m − ( k − i + 1 ) ) × ( l − ( k − i + 1 ) ) n\times m\times l-(n-(k-i+1))\times (m-(k-i+1))\times (l-(k-i+1)) n×m×l−(n−(k−i+1))×(m−(k−i+1))×(l−(k−i+1))。
这篇关于CTS2019 / CTSC2019」随机立方体的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
