[ABC297F] Minimum Bounding Box 2
考虑解决一个稍简单的问题。
给你一个 \(n \times m\) 的矩形棋盘，要在上面放 \(k\) 个棋子，使得矩形 \(4\) 条边上都要有至少一个棋子。问方案数。
样例输入：
2 2 2
样例输出：
2
总方案数 \(C_{n\times m}^k\)。
发现不好做，我们于是试着求解 \(4\) 边上只要有一边上没有棋子的方案数。
发现这是四个非条件的并，那么就可以用容斥原理了。
下文用“上”来代指“如果上边没有棋子”（其他同理），并省略“那么棋子的摆放方案数为”。
-
一条边上没有棋子
- 上，下，\(2C_{(n-1)\times m}^{k}\)（水平方向长 \(m\)，垂直方向长 \(n\)）；
- 左，右， \(2C_{n \times (m-1)}^{k}\)
总方案数是 \(2(C_{(n-1)\times m}^{k} + C_{n\times (m-1)}^{k} )\)。记为 \(A\)。
-
两条边上没有棋子
- 上下，\(C_{(n-2)\times m}^{k}\)
- 左右，\(C_{n\times (m-2)}^{k}\)
- (上/下)(左/右)，\(4C_{(n-1)\times (m-1)}^{k}\)
总方案数是 \(C_{(n-2)\times m}^{k} + C_{n\times (m-2)}^{k} + 4C_{(n-1)\times (m-1)}^{k}\)。记为 \(B\)。
-
三条边上没有棋子
- 上，下，左/右，\(2C_{(n-2)\times (m-1)}^{k}\)
- 左，右，上/下，\(2C_{(n-1)\times (m-2)}^{k}\)
总方案数是 \(2(C_{(n-2)\times (m-1)}^{k} + C_{(n-1)\times (m-2)}^{k})\)。记为 \(C\)。
-
四条边上没有棋子，总方案数：\(C_{(n-2)\times(m-2)}^{k}\)。记为 \(D\)。
-
所以非法方案数为 \(A-B+C-D\)，合法就是 \(C_{n \times m}^k - A + B - C + D\)。
考虑题目问的是期望，我们可以枚举随机矩形的长、宽，然后使其满足 \(4\) 条边上都要有至少一个棋子。
然后这个矩形设长为 \(i\)，宽为 \(j\)，可以出现的位置恰好是 \((n-i+1)(m-j+1)\)，乘上其面积还有出现概率，最后除以总概率。