题解：P3315 [SDOI2014] 酗酒者

f321dd · 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 倍，精度会炸上天。为了保证数值精度，或许无法优化复杂度。