高斯消元法#

高斯消元法（Gauss-Jordan elimination），可以用于解决：线性方程组求解、行列式求值、矩阵求逆等问题。

给定一个线性方程组，要求解。

一些定义#

变量 $=$ 元 $=$ 变元 $=$ 未知数。

对于一个 $m$ 元线性方程组，已知系数 $a_{ij}$​，未知量 $x_i$​，即：

将简记为一个 $n$ 行 $m$ 列的矩阵：

我们称这个矩阵为 系数矩阵。

在系数矩阵右侧，加一列常数项，称其为 增广矩阵：

竖线 $\mid$ 没有其他含义，只是为了区分等式左右两侧。两侧同属一个矩阵。

为了方便表示，后面出现的 $c_i$ 可能会用 $a_{i, m+1}$ 代替。

简单情况#

从简单情况开始考虑，假设恰好 $n=m$，且每个方程都有意义，方程组形如：

矩阵为：

矩阵的左下角都是 $0$.

对于这种倒三角矩阵，最后一行代表的方程为：$a_{nm}\cdot x_m=a_{n,m+1}$，可以直接求出 $x_m=\frac{a_{n, m+1}}{a_{nm}}$.

之后，我们再将 $x_m$ 代入倒数第二行的方程：$a_{n-1,m-1}\cdot x_{m-1}+a_{n-1,m}\cdot x_m=a_{n-1, m+1}$，求出 $x_{m-1}$.

以此类推，就可以求出所有的未知量了。

考虑如何将原矩阵变换为倒三角矩阵。

这就和一般的消元法解方程一样，要让第 $x_i$ 个未知数只存在于前 $i$ 个方程（其它方程中 $x_i$ 系数均为 $0$）.

枚举列，也就是枚举未知数。当我们枚举到第 $c$ 列的时候，我们要让 $\sum_{i=c+1}^{n}[a_{i, c}\neq0]=0$.

所以对于第 $i\in [c+1, n]$ 行，整行一起变换，使 $a_{i,c}=0$：

由于 $\forall j\in[1, c-1]，a_{c, j}=0$，所以上式与 $j\in[c, m+1]$ 是等价的。

之后进行回带，把所有无关项移到等式右边。

double A[MAXN][MAXN], ans[MAXN];
void Gauss() {
	for(int c = 1; c <= n; c++) {
		for(int i = c + 1; i <= n; i++) {
			double t = A[i][c] / A[c][c];
			for(int j = c + 1; j <= n + 1; j++) {
				A[i][j] -= A[c][j] * t;
			}
		}
	}
    for(int i = n; i >= 1; i--) {
        for(int j = i + 1; j <= n; j++) a[i][n + 1] -= a[i][j] * ans[j];
        ans[i] = a[i][n + 1] / a[i][i];
    }
}

提高精度#

在消元过程中，对于第 $i$ 个主元，我们默认选择第 $i$ 行的 $a_{i, i}$ 作为保留的元素。

为了减小误差，我们在第 $i$ 列的 $a_{i, j}(j\geq i)$ 中选一个最大的数作为保留的元素，之后交换第 $i$ 行和第 $j$ 行。

显然，这样有助于精度的控制。

扩大适用范围#

前面的方法基于 $n=m$，且方程组存在唯一解。然而，方程个数与未知数不一定相等，解的个数也不一定唯一，下面给出更普适的方法。

判断解的个数#

容易发现，由 $n$ 个方程构成的 $m$ 元线性方程组，解的个数只可能为：$0, 1, \infty$.

为了方便判断，我们引入自由元的定义：取值不确定的变元。

当我们枚举到第 $i$ 个变量，且前 $i$ 个变量都不是自由元时，如果第 $i\sim n$ 行中这个变量的系数均为 $0$，那么第 $i$ 个变量是自由元。

上面的例子中，$x_3$ 即为自由元。可以发现，当 $x_4, x_5$ 被确定之后，第三行的方程可以记为：

若 $C=0$，则 $x_3$ 可以在 $\Bbb{R}$ 中任取。

若 $C\neq 0$，则 $x_3$ 一定无解，方程组也一定无解。

另外，存在一个自由元，其值可以任取，不代表方程组有无穷组解。因为若有其它变量是无解的，则方程组无解。

出现自由元这种情况，说明有些方程之间是线性相关的，所以加减消元之后就消没了。

解决 $n\neq m$ 的情况#

在枚举变量的过程当中，会发现有些变量是自由元。这时我们应当跳过这一列，并且保持行不变，处理下一个变元。

因此我们用指针 $\operatorname{row}$ 和 $\operatorname{col}$ 表示当前所在的行和列，最后 $\operatorname{row}$ 的位置即为非自由元的个数。

由于遇到所有自由元时，我们都保持行不变，所以可以理解为：我们把所有自由元都挪到了最后面没有被 $\operatorname{row}$ 遍历到的几行当中去。

这可以结合上面 $5\times 5$ 的例子进行理解。

在遇到自由元 $x_3$ 后，跳过第 $3$ 列，保持 $\operatorname{row}$ 不变。所以第 $3$ 行保留的主元是 $x_4$，同理第 $4$ 行保留的主元是 $x_5$.

所以第 $5$ 行即代表第 $x_3$，第 $5$ 行的方程为：$0\times x_3=c_5$.

代码#

下面代码会将所有自由元保留到最后的连续几行。

因此，要判断解的情况，只需要去判断第 $\operatorname{row+1}\sim n$ 行的系数 $c$ 是否为 $0$ 即可。

//高斯消元法，返回-1为无解，0为无穷解，1为唯一解
double A[MAXN][MAXN], ans[MAXN];
int Gauss() {
	int row = 1, max_row;
	for(int col = 1; col <= m; col++) {
		max_row = row;
		for(int i = row + 1; i <= n; i++) { //提高精度 找到一列中值最大的
			if(fabs(A[i][col]) > fabs(A[max_row][col])) max_row = i;
		}
		if(fabs(A[max_row][col]) < eps)
			continue; //如果col是自由元，那么跳过这一列，但行不变
		if(max_row != row) { //swap(当前行，最大值所在的行)
			for(int i = 1; i <= m + 1; i++) swap(A[row][i], A[max_row][i]);
		}
		for(int i = row + 1; i <= n; i++) {
			double t = A[i][col] / A[row][col];
			for(int j = 1; j <= m + 1; j++) {
				A[i][j] -= A[row][j] * t;
			}
		}
		row++;
	}
	row--;
	if(row < n) {
		for(int i = row + 1; i <= n; i++) {
			//如果左边所有系数都是0，等号右边不是0，则无解
			if(abs(A[i][m + 1]) > eps) return -1;
		} //否则有无数解
		return 0;
	}
	for(int i = m; i >= 1; i--) { //回代
		for(int j = i + 1; j <= m; j++) A[i][m + 1] -= A[i][j] * ans[j];
		ans[i] = A[i][m + 1] / A[i][i];
	}
	return 1;
}

高斯-约旦消元法#

高斯-约旦消元法，是高斯消元法的另一个版本，相异之处就是这算法产生出来的矩阵是一个简化行梯阵式，省去了回代过程。

相比起高斯消元法，此算法的效率和精度都比较低，但代码难度也低。

算法思想#

构造方程组矩阵的方法同上，化简后的矩阵形如：

只保留主对角线上的元素。

显然，这样就省去了回代的步骤，直接 $a_{i, i}\cdot x_i=c_i$ 就可以解出所有未知数了。

算法实现#

在上面的高斯消元法中，有这样一句话：

当我们枚举到第 $c$ 列的时候，我们要让 $\sum_{i=c+1}^{n}[a_{i, c}\neq0]=0$.

要想让最终的矩阵只保留主对角线上的元素，我们只需要把这句话改为：

当我们枚举到第 $c$ 列的时候，我们要让 $\sum_{i\neq c}[a_{i, c}\neq0]=0$，也就是直接消掉其他所有行。

double A[MAXN][MAXN], ans[MAXN];
void Gauss_Jordan() {
	for(int c = 1; c <= n; c++) {
		for(int i = c + 1; i <= n; i++) {
			double t = A[i][c] / A[c][c];
			for(int j = c + 1; j <= n + 1; j++) {
				A[i][j] -= A[c][j] * t;
			}
		}
	}
}

扩大适用范围#

在高斯-约旦消元法中，我们同样可以选择每列最大的数作为主元，以提高精度。

同时，我们可以用类似的方法判断方程组解的个数。

两种算法的区别只在第 $\rm{15\sim16}$ 行、第 $33$ 行这两处。

//高斯-约旦消元法，返回-1为无解，0为无穷解，1为唯一解
double A[MAXN][MAXN], ans[MAXN];
int Gauss_Jordan() {
	int row = 1, max_row;
	for(int col = 1; col <= m; col++) {
		max_row = row;
		for(int i = row + 1; i <= n; i++) {
			if(fabs(A[i][col]) > fabs(A[max_row][col])) max_row = i;
		}
		if(fabs(A[max_row][col]) < eps)
			continue; //如果col是自由元，那么跳过这一列，但行不变
		if(max_row != row) { //swap(当前行，最大值所在的行)
			for(int i = 1; i <= n + 1; i++) swap(A[row][i], A[max_row][i]);
		}
		for(int i = 1; i <= n; i++) {
			if(i == row) continue; //每列只保留第row行的元素
			double t = A[i][col] / A[row][col];
			for(int j = 1; j <= m + 1; j++) {
				A[i][j] -= A[row][j] * t;
			}
		}
		row++;
	}
	row--;
	if(row < n) {
		for(int i = row + 1; i <= n; i++) {
			//如果左边所有系数都是0，等号右边不是0，则无解
			if(fabs(A[i][n + 1]) > eps) return -1;
		} //否则有无数解
		return 0;
	}
	for(int i = 1; i <= m; i++) {
		ans[i] = A[i][m + 1] / A[i][i];
	}
	return 1;
}

解异或方程组#

对于异或方程组，高斯消元法同样适用。

在实数方程组中，我们消掉第 $v$ 个变元的方法是：用第 $a$ 行减去第 $b$ 行的 $k$ 倍，使第 $a$ 行第 $v$ 列变为 $0$。

在异或方程组中，若第 $a$ 行第 $v$ 列的值为 $1$，就将第 $a$ 行异或上第 $b$ 行。（按列分别异或）

由于 $x\in\{0, 1\}$，所以 $(a\cdot x)\oplus (b\cdot x)=(a\oplus b)\cdot x$，因此第 $a$ 行异或后的方程是成立的。

注意到异或方程组的增广矩阵是 $01$ 矩阵（矩阵中仅含有 $0$ 与 $1$），所以我们可以使用 C++ 中的 std::bitset 进行优化，将时间复杂度降为 $O(\dfrac{n^2m}{\omega})$，其中 $n$ 为元的个数，$m$ 为方程条数，$\omega$ 一般为 $32$（与机器有关）。

代码#

bitset<MAXN> A[MAXM];
int Gauss() {//A[][]是m行n列的矩阵
	for(int col = 1; col <= n; col++) {
		int x = col;
		while(x <= m && !A[x][col]) x++;
		if(x == m + 1) return 0;
		ans = max(ans, x);
		if(col != x) {//swap(A[x], A[col]);
			bitset<MAXN> tmp = A[x];
			A[x] = A[col]; A[col] = tmp;
		}
		for(int i = 1; i <= m; i++) {
			if(i != col && A[i][col]) A[i] ^= A[col];
		}
	}
	return 1;
}

模意义下的高斯消元 - 模数为质数#

对于模数为合数的情况，会在后面提到。

分析#

注意到，在实数域内的高斯-约旦消元有这样一段代码：

只要把除法操作改为乘逆元即可。

代码#

普通的高斯-约旦消元：

//......
for(int i = 1; i <= n; i++) {
    if(i == row) continue;
    double t = A[i][col] / A[row][col];
    for(int j = 1; j <= m + 1; j++) {
        A[i][j] -= A[row][j] * t;
    }
}
//......
for(int i = 1; i <= n; i++) {
    ans[i] = A[i][n + 1] / A[i][i];
}

模意义下的高斯-约旦消元：

//......
for(int i = 1; i <= n; i++) {
	if(i == row) continue;
	int k = A[i][col] * inv(a[col][col]) % mod;
	for(int j = 1; j <= m + 1; j++) {
		A[i][j] = (A[i][j] + A[col][j] * (mod - k)) % mod;
	}
}
//......
for(int i = 1; i <= n; i++) {
    ans[i] = A[i][n + 1] * inv(A[i][i]) % mod;
}

模意义下的高斯消元 - 模数为合数#

模数为合数时，有些数没有逆元，需要另寻方法。

分析#

对于模数为合数的情况，我们使用类似辗转相除的方法。

对于两行 $a, b$，现在要消去变元 $c$。

在辗转相除法时，我们会用 $a\leftarrow a\bmod b$，但现在要同时操作一整行，没法直接取模，所以要模拟一下取模的过程。

我们每次将 $a$ 减去 $b$ 的尽可能多倍（$k\in \Bbb{Z}^{+}$），使仍然保持 $a_c\geq 0$，之后交换 $a, b$，重复操作，直到 $a_c=0$.

具体地，所减去的倍数 $k=\lfloor\dfrac{a_c}{b_c}\rfloor$.

代码#

辗转相除法就不用每次找最大的换上去了，因为不需要控制精度，都是整数。

void Gauss() {
	for(int col = 1; col <= n; col++) {
		for(int row = col + 1; row <= n; row++) {
			while(a[row][col]) {
				int t = a[col][col] / a[row][col];
				for(int i = 1; i <= n; i++) {
					a[col][i] = (a[col][i] + a[row][i] * (p - t)) % p;
				}
				for(int i = 1; i <= n; i++) swap(a[col][i], a[row][i]);
			}
		}
	}
}

[JSOI2008] 球形空间产生器#

题意#

给定一个 $n$ 维超球上的 $n+1$ 个点的坐标，求球心坐标。保证有唯一解。

$n<=10$，坐标绝对值为 $20000$ 以内实数。

球心：到球面任意一点距离都相等的点。

距离：若两点坐标为 $A(a_1, a_2\cdots, a_n)$，$B(b_1, b_2, \cdots, b_n)$，那么：

$$\operatorname{dis(A, B)}=\sqrt{(a_1-b_1)^2+(a_2-b_2)^2+\cdots+(a_n-b_n)^2}$$

分析#

设圆心坐标为 $(x_1, x_2, \cdots, x_n)$，那么容易列出一个方程组：

其中 $C$ 就代表 $n$ 维超球的半径。

但这不是一个线性方程组，没法快速求解。

又注意到，求出圆心坐标，只有 $n$ 个未知数，而现在能列出 $n+1$ 个方程，所以考虑进行差分。

差分#

对于其中的第 $p$ 个方程，我们对其进行整理，变为：

同理有：

我们用 $(p+1)-(p)$，得到：

以此类推，我们能得到 $n$ 个形如 $(*)$ 的线性方程，于是问题可以用高斯消元求解。

最终的系数矩阵为：

代码#

Ubuntu Pastebin ↗，应该不用看吧？

[SDOI2010] 外星千足虫#

题意#

给定 $n$ 个点，按点权的奇偶性分为两类。

给定 $m$ 次统计数据，每条数据包含：若干个被选中点，以及被选中的点权和的奇偶性。

请判断每个点权的奇偶性。

题目保证有解，若解不唯一，输出 $\rm{Cannot\;Determine}$.

分析#

设 $a_{i, j}\in\{0, 1\}$ 表示第 $i$ 条数据中，第 $j$ 个点是否被选中， $b_i\in \{0, 1\}$ 表示第 $i$ 次统计结果的奇偶性。

设 $x_i=w_i\bmod 2$ 表示第 $i$ 个点权的奇偶性。

那么有同余方程组：

注意到，方程左右两侧都只需要考虑二进制下的第一位，因此可以转化为一个异或方程组：

解异或方程组即可。

其他要求#

题目要求：输出一个不超过 $M$ 的正整数 $K$，表明在第 $K$ 次统计结束后就可以确定唯一解。

对于这个要求，我们只需要在高斯消元时每次对行取 $\max$ 即可，详见下面代码的第 $7$ 行。

在下面代码的消元过程中，对于第 $\rm{col}$ 列，我们会贪心地找到编号最小的 $x$ 满足 $A[x][col]=1$.

所以，要想确定方程的解，至少要通过前 $x$ 条统计数据，否则第 $\rm{col}$ 个变量就无法求解。

Band-Matrix#

简介#

这是个在 OI 中很经典的 trick。

Band-Matrix，带状矩阵，对这种矩阵进行高斯消元时，可以进行优化。

顾名思义，带状矩阵是长条形的，差不多是这样：

白色部分为 $0$，红色部分有数，其它部分先不管。

这样中间形成了一个宽度为 $d$ 的带，这样消元的复杂度可以降到 $\mathcal{O}(nd^2)$.

常见于一些期望DP的问题。

消元流程#

在图中，绿色节点是我们要保留的主元。

注意到在这种形式下，对于任意的 $A_{i, i}$，其向下、向右的有效数字个数均 $\leq d-1$.

所以假设现在要消第 $i$ 列，那么从第 $i$ 行开始往下枚举 $d-1$ 行，每行往右消 $d$ 个数字，最后能得到一个倒三角矩阵。

之后回代。回代过程的复杂度最高是 $\mathcal{O}(n^2)$ 的，不是复杂度瓶颈，但也可以根据带状矩阵的形状优化。

判断无解/存在自由元#

大部分题好像都有解，下面的参考资料中也有讲。

细节#

如果 $n$ 太大，二维数组开不出来，可以只记录带状矩阵的部分，也可以用 unordered_map.

参考资料#

浅谈高斯消元拓展之 band-matrix - Froggy 珂学家的博客 ↗

P5516 [MtOI2019]小铃的烦恼#

题意#

给定长度为 $n$ 的序列，第 $i$ 个元素为 $a_i$.

每次随机取出一个有序数对 $(x, y)(x\neq y)$，然后以 $s_{x, y}$ 的成功概率将 $a_x$ 变为 $a_y$（若不成功则不变）。

要让全部元素都相同，求期望次数。

$1\leq a_i \leq26$，$n\leq 2\times 10^3$.

对于所有数据，满足 $(\sum\limits_{a=1}^{n}\sum\limits_{b=1}^n s_{a, b})=n^2$.

分析#

高斯消元？看不出来有方程。

由于 $(\sum\limits_{a=1}^{n}\sum\limits_{b=1}^n s_{a, b})=n^2$ ，显然每个 $s_{i, j}$ 都恒为 $1$。这表明对于选出的任意两个数 $x, y$，每次操作都能成功。

然而这并没有使这题与概率无关，因为 $x, y$ 的选取仍然是随机的。

考虑到最后全部的元素会相同，但不知道都变成什么元素，因此我们先枚举目标元素**（最后剩下的元素）。

下面开始推式子。

概率#

对序列的每次操作，可能会使目标元素的个数增加：$-1/0/1$ 个。

可以发现，一种元素最后成为目标元素的概率，取决于一开始序列中有多少个这种元素。

因此，下面的分析建立在已经确定目标元素的基础上，换言之，只关注有多少个目标元素。

设 $p[i]$ 表示：此时有 $i$ 个目标元素，全部元素都变成当前选取的目标元素的概率。

那么：

方程代表：从有 $i$ 个目标元素的状态为基础，操作一次，产生的三种可能情况。

要让目标元素个数 $\pm 1$，就要从 $i$ 个数中选一个，再从其他的 $n-i$ 个数中选一个。

从 $n$ 个数中随机选取两个的方案数是 $n(n-1)$，因此目标元素个数 $\pm 1$ 的概率均为 $\frac{i(n-i)}{n(n-1)}$.

而目标元素个数不变的概率，就是 $1$ 减去前两种情况剩下的概率。

对方程进行整理，设 $k=\frac{i(n-1)}{n(n-1)}$，那么有：

把 $k$ 约掉：

也就是：

这说明 $p$ 的相邻两项差值相同，$p$ 是等差数列。

又因为显然， $p[0]=0$，$p[n]=1$，可以得到一个非常简单的形式：

在此基础上，我们继续研究期望。

期望#

期望的分析要简单一些，设 $f[i]$ 表示：当前有 $i$ 个目标元素，使全部元素都变成目标元素的期望步数。

我们只关心能使目标元素个数变化的操作。可以发现，目标元素变化（$+1/-1$）的概率为 $2\frac{i(n-i)}{n(n-1)}$.

因此，操作一次，期望变化 $\frac{2i(n-i)}{n(n-1)}$；变化为 $1$，期望次数就是 $\frac{n(n-1)}{2i(n-i)}$.

所以得到和期望相关的方程：

方程整体的含义是：当前状态下有 $i$ 个目标元素，要让个数变化 $1$。第一项就是变化 $1$ 的期望操作次数，后两项分别是个数 $+1/-1$ 后的情况。

$f[i]$ 乘上了 $p[i]$，因为 $p[i]$ 的概率最终能移动到目标元素，$f[i]$ 的期望贡献只有 $p[i]\times f[i]$。

由于 $+1/-1$ 的概率相同，所以两种情况的系数都是 $\frac{1}{2}$.

同理，期望操作也要乘上 $p[i]$，因为只有 $p[i]$ 的概率，会向目标方向转移。（或者也可以把左边的 $p[i]$ 除过去，用另一种方法理解）

把 $p[i]=\frac{i}{n}$ 代入，整理得到：

又因为 $f[n]=0$， $i\in[1, n-1]$.

所以现在得到了 $n-1$ 个方程，$n-1$ 个未知数，可以高斯消元解方程组。

然而本题数据范围 $n\leq 2\times 10^3$，$\mathcal{O}(n^3)$ 的高斯消元不可行，下面是一些消元技巧。

高斯消元#

每个方程只有三项是有系数的，矩阵长这样：

可以发现，对第 $i$ 个元，只有$i-1$，$i$ 和 $i+1$ 行的系数非零。所以如果用高斯-约旦消元法，只需要消第 $i-1$ 和 $i+1$ 行的就行了。

又因为每行只有三个变元的系数和一个等号右边的系数，所以这样的时间复杂度是 $\mathcal{O}(n)$.

此外，空间复杂度也能比较轻易地优化到 $\mathcal{O}(n)$，可以参考其他题解。

代码#

Ubuntu Pastebin ↗

概率都是 $1.00$，可以不用输入。注意数组要用 double。

参考资料#

a_forever_dream的博客 - CSDN博客 ↗

P3232 - [HNOI2013]游走#

题意#

给定一个 $n$ 个点 $m$ 条边的无向连通图，顶点从 $1$ 编号到 $n$，边从 $1$ 编号到 $m$。

小 Z 在该图上进行随机游走，初始时小 Z 在 $1$ 号顶点，每一步小 Z 以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小 Z 到达 $n$ 号顶点时游走结束，总分为所有获得的分数之和。

现在，请你对这 $m$ 条边进行编号，使得小 Z 获得的总分的期望值最小。

求最小期望值。

$2\leq n\leq 500$，$1\leq m\leq 125000$，无重边无自环。

分析#

设边 $(i,j)$ 的期望经过次数为 $E_{(i, j)}$，答案即 $\sum E_{(i, j)} v_{(i, j)}$，因为每条边的边权 $v$ 可以自己定，容易想到贪心。

先算出期望经过次数，然后让经过次数最大的边的编号最小。就是一个期望DP。

期望DP#

由于 $m$ 比较大，并且我们不会列出只和 $E$ 相关的方程式，所以先处理点。

设 $f_i$ 表示从 $1$ 走到 $n$ 的过程中，经过点 $i$ 的期望次数。 用其表示 $E$，

经过一条边有两种可能的方向，分别考虑从 $i\rightarrow j$ 和 $j\rightarrow i$。

首先根据题意要求起点不能为 $n$，从 $i$ 出发，下一次恰好走到 $j$ 的概率即为 $\dfrac{1}{\operatorname{deg}_i}$。

下面计算 $f_i$，和上面类似地，有：

相当于对于每个 $i$，枚举上一个经过的点 $j$，从 $j$ 走到 $i$ 的概率为 $\dfrac{1}{\operatorname{deg}_j}$.

对于节点 $1$，初始时一定会经过一次，所以 $f_i$ 要多 $1$.

对于节点 $n$，走到之后就不能出去了，所以枚举 $j$ 时 $j\neq n$.

于是我们得到了 $n$ 个有关 $f$ 的方程，转移有后效性，用高斯消元求解即可。

时间复杂度：$\mathcal{O}(n^3)$.

代码#

Ubuntu Pastebin ↗

模型#

这种模型在概率期望题中很常见，只不过表达形式有所不同。

给定若干个点，点 $u$ 有 $P_{u, v}$ 的概率通向点 $v$。终点或某些其他点，进去之后就不能出来。

求从点 $S$ 出发，走到点 $T$ 的期望步数。

这个图如果不是 $\rm{DAG}$ 的话就不能用 DP 解决，只能列方程，用高斯消元。

设 $E_i$ 表示从 $i$ 走到 $T$ 的期望步数，方程形如：

就是所有后继状态的期望步数乘上对应转移概率，再求和。

这道题是算期望经过次数，不是步数，所以转移略有不同。后面的题大多都是这种模型。

参考资料#

治疗之雨题解 - shadowice1984 的博客 ↗

CF24D - Broken robot#

题意#

$n$ 行 $m$ 列的矩阵，$(1,1)$ 是左上角，$(n,m)$ 是右下角。

初始状态在 $(x,y)$。每次等概率向左，右，下走或原地不动，但不能走出去。

**等概率：**若其位于第一列，只能向右、下走或原地不动，则选择这三种的概率均为 $\frac{1}{3}$.

求走到最后一行期望的步数，保留四位小数。

$1\leq n, m\leq 10^3$.

分析#

令 $f_{i,j}$ 表示从位置 $(i,j)$ 走到最后一行，所需行动次数的期望值。目标是要求出 $f_{x, y}$.

首先，初始状态为：$\forall j\in[1,m],f_{n,j}=0$。

不在最后一行时：

在第一列不能再向左走，在第 $m$ 列不能再向右走。

暴力高斯消元，时间复杂度 $\mathcal{O}(n^6)$，不能接受。空间复杂度 $\mathcal{O}(n^4)$，更不能接受。

消元#

显然第 $i$ 行的状态只与 $i$ 和 $i+1$ 行有关，在行维度上，其满足无后效性。我们还知道 $f_n=0$，所以从下往上逐行计算。

于是方程中 $f_{i+1,j}$ 是已知的常数，直接移到等式右侧，得到方程组：