题目描述：
有一个\(n×n(n≤300)\)的棋盘和\(1~m(n^2≤m≤100000)\) 这些数字。棋盘首先会被随机生成,即从“填着值域\(1 \sim m\)的数字且\(n^2\)个数字两两不同”的所有方案中随机选一个。
然后你会从\(1\sim m\)中随机选出\(k(n≤k≤m)\)个不同的数,并且报出来。报出一个数字,如果在棋盘中出现过,就把对应格涂黑。设\(t\)为完全染黑的行数、完全染黑的列数的和,你的最终得分为\(2^t\)求得分的期望。如果超过\(10^{99}\),输出\(1e99\)
思路：
观察到题目中有一个非常恼人的 \(2^r\)。我们考虑一下这个东西的实际含义：从 \(t\) 个染黑的行和列中选一个子集（一些行+一些列）的方案数
所以我们不妨去计算对于一个有 \(r\) 行，\(c\) 列的集合是多少集合的子集，这个就是这个集合对答案的贡献。
首先我们思考一下总方案数是多少：\(\binom{m}{n^2}\times \binom{m}{k}\)
然后我们枚举选了 \(r\) 行 和 \(c\) 列，总贡献是多少：\(\sum\limits_{r=0}^{n}\sum\limits_{c=0}^{n}\binom{m}{n^2}\binom{n}{r}\binom{n}{c}\binom{m-num}{k-num},num=(r+c)\times n-r-c\)
简单解释一下这个式子是什么意思：首先你需要选一个棋盘，方案数 \(\binom{m}{n^2}\)；然后你要选一些行和一些列作为被涂黑的行和列: \(\binom{n}{r}\binom{n}{c}\)；然后我们这个
所以总方案数为 \(Ans=\frac{\sum\limits_{r=0}^{n}\sum\limits_{c=0}^{n}\binom{m}{n^2}\binom{n}{r}\binom{n}{c}\binom{m-num}{k-num}}{\binom{m}{n^2}\binom{m}{k}}=\frac{\sum\limits_{r=0}^{n}\sum\limits_{c=0}^{n}\binom{n}{r}\binom{n}{c}\binom{m-num}{k-num}}{\binom{m}{k}}\)
标签：Bingo,CF457D,limits,sum,num,binom,棋盘,染黑 From： https://www.cnblogs.com/Candycar/p/17827776.html