方法

顾名思义解这样一个方程组：

其中 $d$d 称为带宽
对于传统的高斯消元(不管是回代型还是高斯-约旦型)都是 $O(n^3)$O(n3)
但是如果求某些特殊问题(如概率dp，期望dp)可以做到 $O(nd^2)$O(nd2)
我们每次沿对角线对一个 $d*d$d∗d 的矩阵进行消元：

注意每次 $d*d$d∗d 的矩形只消第一列，即：

最后得到这些格子还有系数：

然后回代即可
时间复杂度每个矩形高斯消元是 $O(d^2)$O(d2) 有 $O(n)$O(n) 个矩形，所以解方程为 $O(nd^2)$O(nd2)，回代每个元回代 $O(d)$O(d) 次，回代时间复杂度为 $O(nd)$O(nd)
所以总的时间复杂度为 $O(d^2)$O(d2)

适用范围

这时会发现一个很严重的问题
如果消元时候对角线上系数消为 $0$0 怎么办？
我们并不能交换行列
这是实际存在的，但对于一些场合并不会出现这样的问题
一般而言用作高斯消元的时候是解概率dp或期望dp
如果最终每个变量都有解（矩阵满秩）那就不会出现这样的问题
首先针对 $dp$dp 满秩的矩形的有个特性：
对于前 $i$i 行将 $[i+1,n]$[i+1,n] 的变量看为参数移项后满秩
就是假设提前知道 $[i+1,n]$[i+1,n] 变量的值代入
因为这是dp（有点难讲述）
然后考虑归纳证明前 $i*i$i∗i 矩形中对角线消元时不会为 $0$0
已知 $(i-1)*(i-1)$(i−1)∗(i−1) 矩形能消成只有对角线上有系数的矩阵，
考虑由 $(i-1)$(i−1) 到 $i$i ，$x_i$xi​ 由参数变为变量从每一行最右边的值移过来，因为 $dp$dp 的实际意义能得出前 $i$i 行的矩阵必然满秩，对于第 $i$i行只有第 $i$i个位置有系数，解出 $i$i 后回代即可

思考

能对部分选主元的题目进行简化