上三角矩阵高斯消元的优化

P4457 [BJOI2018]治疗之雨

$n\le 1500$，不能直接$n^3$高斯消元。然而这道题需要高斯消元的那个矩阵很特殊，近似上三角矩阵，大概长这样（$1$表示值不为$0$）：

$$\begin{bmatrix} 1 & 1 & 0 & 0 & 0 & \cdots & 0 \\ 1 & 1 & 1 & 0 & 0 & \cdots & 0 \\ 1 & 1 & 1 & 1 & 0 & \cdots & 0 \\ 1 & 1 & 1 & 1 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ \end{bmatrix}$$

如果我们从第一行开始消，那么消完第一行后，矩阵就变成这样的了：

$$\begin{bmatrix} 1 & 1 & 0 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 1 & 1 & 0 & \cdots & 0 \\ 0 & 1 & 1 & 1 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ \end{bmatrix}$$

这个时候我们再用第二行去消：

$$\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 1 & 0 & 0 & \cdots & 0 \\ 0 & 0 & 1 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & 1 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ \end{bmatrix}$$

然后是第三行：

$$\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 0 & 0 & 0 & \cdots & 0 \\ 0 & 0 & 1 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 0 & 1 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ \end{bmatrix}$$

这个时候轮到第四行……我们发现，我们拿去消元的那一行，总是只有两个元素不为$0$（算上常数项就是$3$个）。我们只用不为$0$的元素去消元，每次消一行的时间就从$O(n)$降到了$O(1)$的，总复杂度降到$O(n^2)$。