高斯消元的线性技巧

朴素的高斯消元是 \(\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)\) 。

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