$Gauss$

——浅谈高斯消元方程组的构造

我们以一道题为例：

本题要求求解路径上 $xor$ 的期望值，那么根据期望是线性的套路性质，我们可以考虑求出每一位上为 $1$ 的期望，乘上使用次数就是答案。

所以我们根据这个性质，设 $f_i$ 表示从 $i$ 这一位为 $1$ 的概率。

那么从其他转移过来为 $0$ 的概率是 $f_i$ ，为 $1$ 的概率为 $1 - f_i$ 。

有
$$
f_i = \frac{\sum_{E(u, v) = 0} f_i + \sum_{E(u, v) = 1} (1 - f_i)}{du_i}
$$
移个项
$$
f_i \times du_i - \sum_{E(u, v) = 0} f_i + \sum_{E(u, v) = 1} f_i = \sum_{E(u, v) = 1}
$$
然后就到了构造高斯消元方程的时候。

也就是我们将高斯消元的系数填入矩阵中，再利用高斯消元求解。

我们将系数直接放入矩阵
$$
\begin{bmatrix}
du_{1_1} - \sum_{E_{1_1}(u, v) = 0} + \sum_{E_{1_1}(u, v) = 1} & du_{1_2} - \sum_{E_{1_2}(u, v) = 0} + \sum_{E_{1_2}(u, v) = 1} & \ldots
\\
du_{2_1} - \sum_{E_{2_1}(u, v) = 0} + \sum_{E_{2_1}(u, v) = 1} & du_{2_2} - \sum_{E_{2_2}(u, v) = 0} + \sum_{E_{2_2}(u, v) = 1} & \ldots
\\
\ldots
\\
du_{n - 1_1} - \sum_{E_{n - 1_1}(u, v) = 0} + \sum_{E_{n - 1_1}(u, v) = 1} & du_{n - 1_2} - \sum_{E_{n - 1_2}(u, v) = 0} + \sum_{E_{n - 1_2}(u, v) = 1} & \ldots
\end{bmatrix}
=
\begin{bmatrix}
\sum_{E_1(u, v) = 1}
\\
\sum_{E_2(u, v) = 1}
\\
\ldots
\\
\sum_{E_{n - 1}(u, v) = 1}
\end{bmatrix}
$$
为什么矩阵长成这样？

因为在本题中，对于每一位，他的状态都不同， $E(u, v)$ 的情况也都不同，所以构造出来了这样的方程。

那么，代码实现就简单了，设 $A_{i, j}$ 表示初始矩阵， $A{i, n + 1}$ 表示答案，对于每一位，我们记一个 $w$ 表示这一位的情况，初始赋值 $A_{u, u} = du_i$ ，如果 $E(u, v) = 0$ 那么 $A_{u, v} - 1$ ，否则 $A_{u, v} + 1$ ，并使 $A_{u, n + 1} + 1$ ，就构造出了高斯消元的矩阵，然后套上模板即可。

特别的， $A_{n, n} = 1$ ， $n \to n$ 的概率是 $1$ 。