CVBB ACM Team

假设我们在一个网格图上定义了一些转移，我们要对这个线性方程组做高斯消元。注意到这个矩阵非常稀疏，即每个方程至多只有 $5(9)$ 个变元。因此我们可以只维护非零的系数。我们证明，如果按照 $(0,0),\cdots,(0,m-1),\cdots,(n-1,0),\cdots,(n-1,m-1)$ 的顺序消元的话，时间复杂度为 $\mathcal{O}(nm^{3})$。

以四连通为例，我们很容易归纳地证明，每个点所代表的方程在任何时刻都只有不超过 $\mathcal{O}(m)$ 的变元，$(x,y)$ 最终被前面的方程消完后，剩下的变元是 $(x,y),(x,y+1),\cdots,(x,m-1),(x+1,0),(x+1,1),\cdots,(x+1,y)$。

八连通也是类似的，最后剩下的变元还要加上一个 $(x+1,y+1)$。

在消元的过程中我们还会发现，一个方程最多也只需要去消后面的 $\mathcal{O}(m)$ 个方程（大约是 $2m$ 个），因此总复杂度是 $\mathcal{O}(nm^{3})$。

事实上，我们可以将矩阵转置，将复杂度降为 $\mathcal{O}(nm\min^{2}(n,m))$。