自动搬运

查看原文

来自洛谷，原作者为

	f321dd **

搬运于2025-08-24 21:47:39，当前版本为作者最后更新于2024-11-14 09:35:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

以下设 $n \le m$。

这题的数据范围比较令人迷惑。由于询问的起点和终点都不固定，每次询问都只能整体重新计算，或许没有办法优化。但是其实 $\Theta(qn^3m)$ 的算法就可以通过，实际数据中 $q$ 最大只有 $25$。

首先列出期望方程。考虑进行高斯消元，初始第 $i$ 个变量只和第 $i-n, i-1, i+1, i+n$ 个变量有关，由于网格图的结构，在高斯消元中消去一个变量始终只会影响之后的 $n$ 个变量。这样消元的复杂度是 $\Theta(n^3m)$。

在 Circles of Waiting 一题中也可以使用同样的方法，不过其实本题出现得更早。然而那个题可以使用主元法，将复杂度进一步降低到 $\Theta(n^3)$，本题却完全不能使用。因为本题是浮点数计算，如果使用主元法，每经过一列数值的规模就会增加约 $4$ 倍，精度会炸上天。为了保证数值精度，或许无法优化复杂度。