U471725题解

这题比较简单，难度大约普及-到普及/提高-。这题涉及到的就是数学期望。

针对 $20\%$ 的数据：

大暴力，时间复杂度 $O(nmk)$。

针对 $40\%$ 的数据：

大暴力带点常数优化，时间复杂度依然 $O(nmk)$。

针对 $60\%$ 的数据：

注意到每次射箭的期望得分是相同的，时间复杂度 $O(nm)$。

或者推出数学式子但是没想到期望得分相同，时间复杂度 $O(k)$。

针对 $100\%$ 的数据：

$O(nm)$ 和 $O(k)$ 的算法都在 50ms 的时限下光荣落败（如果 1s 就可能可以完成）。考虑推式子，期望应该是 $\dfrac{得分和}{2nm}$，即 $\dfrac{\sum_{1 \le i \le n,1 \le j \le m}{ij}}{2nm}$，由于二阶和可以拆分为两个一阶和的乘积，所以就是 $\dfrac{(\sum_{i=1}^n{i})(\sum_{j=1}^m{j})}{2nm}$，就是 $\dfrac{nm(n+1)(m+1)}{8nm}$，所以就是 $\dfrac{(n+1)(m+1)}{8}$，因为射 $k$ 次箭，所以答案应该是 $\dfrac{k(n+1)(m+1)}{8}$，时间、空间复杂度 $O(1)$。