高斯消元的线性技巧

朴素的高斯消元是 $\mathcal{O}(n^3)$ 的，算法原理参考 浅谈高斯消元

而在一些题目中，比如 洛谷P5516 [MtOI2019] 小铃的烦恼 ，实际上我们有一种线性的技巧。

---

设 $a_i,b_i,c_i$ 都是关于 $i$ 的函数或常数，$k$ 为常数，递推式（通常是概率或者期望的dp式子）

$$f_0=0,~f_n=k\\f_i = a_if_{i-1}+b_if_{i+1}+c_i (1\le i < n)$$

所对应的矩阵形如

$$\begin{bmatrix} 1 & -a_1 & & & & & c_1\\[6pt] -a_2 & 1 & -b_2 & & & & c_2\\[6pt] & -a_3 & 1 & -b_3 & & & c_3\\[6pt] & & & \ddots && &\vdots\\[6pt] & & & -a_{n-1} & 1 & -b_{n-1} &c_{n-1}\\[6pt] & & & && 1 & k \end{bmatrix}$$

方便起见，我们先把系数的负号去了

$$\begin{bmatrix} 1 & x_1 & & & & & c_1\\[6pt] x_2 & 1 & x_3 & & & & c_2\\[6pt] & x_4 & 1 & x_5 & & & c_3\\[6pt] & & & \ddots && &\vdots\\[6pt] & & & x_{2n-4} & 1 & x_{2n-3} &c_{n-1}\\[6pt] & & & & x_{2n-2} & 1 & k \end{bmatrix}$$

用第一行消第二行的 $x_2$

$$\begin{bmatrix} 1 & x_1 & & & & & c_1\\[6pt] & 1 - x_1x_2 & x_3 & & & & c_2-x_2c_1\\[6pt] & x_4 & 1 & x_5 & & & c_3\\[6pt] & & & \ddots && &\vdots\\[6pt] & & & x_{2n-4} & 1 & x_{2n-3} &c_{n-1}\\[6pt] & & & & x_{2n-2} & 1 & k \end{bmatrix}$$

干脆把第二个系数也去掉

$$\begin{bmatrix} 1 & x_1 & & & & & c_1\\[6pt] & 1 & \frac{x_3}{1-x_1 x_2} & & & & \frac{c_2-x_2c_1}{1-x_1x_2}\\[6pt] & x_4 & 1 & x_5 & & & c_3\\[6pt] & & & \ddots && &\vdots\\[6pt] & & & x_{2n-4} & 1 & x_{2n-3} &c_{n-1}\\[6pt] & & & & x_{2n-2} & 1 & k \end{bmatrix}$$

以此类推，我们可以将整个矩阵转变成

$$\begin{bmatrix} 1 & k_1 & & & & & d_1\\[6pt] & 1 & k_2 & & & & d_2\\[6pt] & & 1 & k_3 & & & d_3\\[6pt] & & & \ddots && &\vdots\\[6pt] & & & & 1 & k_{n-1} &d_{n-1}\\[6pt] & & & & & 1 & k_n \end{bmatrix}$$

其中 $k_n$ 是 $\mathcal{O}(1)$ 可以算出的，根据之前的 $k$​​ 。

那么高斯消元的过程就变简单了。我们只需要两个数组 $k_i$ 和 $d_i$ 。

过程比朴素的高斯消元简单多了，只需要扫一遍，时间复杂度 $\mathcal{O}(n)$ 。

实现代码的话参考一开始给的题目链接即可。