高斯消元

高斯消元法

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

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

一些定义

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

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

$$
\left\{
\begin{array}{}
a_{1,1}x_1+a_{1,2}x_2+\cdots+a_{1,m}x_m=c_1 &(1)\\
a_{2,1}x_1+a_{2,2}x_2+\cdots+a_{2,m}x_m=c_2 &(2)\\
\cdots\\
a_{n,1}x_1+a_{n,2}x_2+\cdots+a_{n,m}x_m=c_n &(n)
\end{array}
\right.
$$

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

$$
\left[\begin{matrix}
a_{1,1} & a_{1,2} & \cdots & a_{1,m} \\
a_{2,1} & a_{2,2} & \cdots & a_{2,m} \\
\cdots & \cdots & \cdots & \cdots \\
a_{n,1} & a_{n,2} & \cdots & a_{n,m}
\end{matrix} \right]
$$

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

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

$$
\left[\begin{matrix}
a_{1,1} & a_{1,2} & \cdots & a_{1,m} \\
a_{2,1} & a_{2,2} & \cdots & a_{2,m} \\
\cdots & \cdots & \cdots & \cdots \\
a_{n,1} & a_{n,2} & \cdots & a_{n,m}
\end{matrix} \middle|
\begin{matrix}
c_1 \\
c_2 \\
\cdots\\
c_n
\end{matrix} \right]
$$

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

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

简单情况

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

$$
\left\{
\begin{array}{r}
&a_{1,1}x_1&+ &a_{1,2}x_2&+\cdots+ &a_{1, n-1}x_{n-1} &+ &a_{1,n}x_n=c_1 &(1)\\
&0\cdot x_1&+ &a_{2,2}x_2&+\cdots+ &a_{2, n-1}x_{n-1} &+ &a_{2,n}x_n=c_2 &(2)\\
&0\cdot x_1&+ &0\cdot x_2&+\cdots+ &a_{3, n-1}x_{n-1} &+ &a_{3,n}x_n=c_2 &(3)\\
&&&&+\cdots+\\
&0\cdot x_1&+ &0\cdot x_2&+\cdots+ &0\cdot x_{n-1} &+ &a_{n,n}x_n=c_n &(n)
\end{array}
\right.
$$

矩阵为:

$$
\left[\begin{matrix}
a_{1,1} & a_{1,2} & \cdots & a_{1,n-1} & a_{1,n} \\
0 & a_{2,2} & \cdots & a_{2,n-1} & a_{2,n} \\
0 & 0 & \cdots & a_{3,n-1} & a_{3,n} \\
\cdots & \cdots & \cdots & \cdots & \cdots \\
0 & 0 & \cdots & 0 & a_{n,n}
\end{matrix} \middle|
\begin{matrix}
a_{1,n+1} \\
a_{2,n+1} \\
a_{3,n+1} \\
\cdots\\
a_{n,n+1}
\end{matrix} \right]
$$

矩阵的左下角都是 $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,m+1],\quad a_{i, j}\leftarrow a_{i, j}-a_{c, j}\cdot\frac{a_{i, c}}{a_{c, c}}
$$

由于 $\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$ 个变量是自由元。

$$
\left[\begin{matrix}
a_{1,1} & a_{1,2} & a_{1, 3} & a_{1,4} & a_{1,5} \\
0 & a_{2,2} & a_{2, 3} & a_{2,4} & a_{2,5} \\
0 & 0 & \color{red}{0}& a_{3,4} & a_{3,5} \\
0 & 0 & 0 & a_{4,4} & a_{4,5} \\
0 & 0 & 0 & 0 & a_{5,5}
\end{matrix} \middle |
\begin{matrix}
c_{1} \\
c_{2} \\
c_{3} \\
c_{4} \\
c_{5}
\end{matrix} \right]
$$

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

$$
0\cdot x_3=c_3-x_4\cdot a_{3, 4}-x_5\cdot a_{3, 5}=C
$$

若 $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;
}

高斯-约旦消元法

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

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

算法思想

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

$$
\left[\begin{matrix}
a_{1,1} &0 & 0 &\cdots & 0 & 0 \\
0 & a_{2,2} & 0 &\cdots & 0 & 0 \\
0 & 0 &a_{3,3} &\cdots & 0 & 0 \\
\cdots &\cdots &\cdots &\cdots &\cdots & \cdots \\
0 & 0 &0 &\cdots & 0 & a_{n,m}
\end{matrix} \middle|
\begin{matrix}
c_{1} \\
c_{2} \\
c_{3} \\
\cdots\\
c_{n}
\end{matrix} \right]
$$

只保留主对角线上的元素

显然,这样就省去了回代的步骤,直接 $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)$,那么容易列出一个方程组:

$$
\left\{
\begin{array}{}
\sum_{i=1}^n(a_{1, i}-x_i)^2=C^2 &(1)\\
\sum_{i=1}^n(a_{2, i}-x_i)^2=C^2 &(2)\\
\cdots&\cdots\\
\sum_{i=1}^n(a_{n, i}-x_i)^2=C^2&(n)\\
\sum_{i=1}^n(a_{n+1, i}-x_i)^2=C^2&(n+1)\\
\end{array}
\right.
$$

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

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

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

差分

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

$$
\sum_{i=1}^{n}{{a_{p, i}}^2}+\sum_{i=1}^{n}{{x_i}^2}-\sum_{i=1}^{n}{2\cdot a_{p, i}\cdot x_i} \tag{p}
$$

同理有:

$$
\sum_{i=1}^{n}{{a_{p+1, i}}^2}+\sum_{i=1}^{n}{{x_i}^2}-\sum_{i=1}^{n}{2\cdot a_{p+1, i}\cdot x_i} \tag{p+1}
$$

我们用 $(p+1)-(p)$,得到:

$$
\sum_{i=1}^{n}{2(a_{p, i}-a_{p+1, i})x_i}=\sum_{i=1}^{n}{({a_{p, i}}^2-{a_{p+1, i}}^2)} \tag{*}
$$

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

最终的系数矩阵为:

$$
\left[\begin{matrix}
2(a_{1, 1}-a_{2, 1}) & 2(a_{1, 2}-a_{2, 2}) & \cdots & 2(a_{1, n}-a_{2, n}) \\
2(a_{2, 1}-a_{3, 1}) & 2(a_{2, 2}-a_{3, 2}) & \cdots & 2(a_{2, n}-a_{3, n}) \\
\cdots & \cdots & \ddots & \cdots \\
2(a_{n, 1}-a_{n+1, 1}) & 2(a_{n, 2}-a_{n+1, 2}) & \cdots & 2(a_{n, n}-a_{n+1, n})
\end{matrix} \middle|
\begin{matrix}
\sum_{j=1}^n({a_{1, j}}^2-{a_{2, j}}^2) \\
\sum_{j=1}^n({a_{2, j}}^2-{a_{3, j}}^2) \\
\vdots\\
\sum_{j=1}^n({a_{n, j}}^2-{a_{n+1, j}}^2)
\end{matrix} \right]
$$

代码

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$ 个点权的奇偶性。

那么有同余方程组:

$$
\left\{
\begin{array}{}
a_{1, 1}x_1+a_{1, 2}x_2+\cdots+a_{1, n}x_n=b_1\pmod{2} &&(1)\\
a_{2, 1}x_1+a_{2, 2}x_2+\cdots+a_{2, n}x_n=b_2\pmod{2} &&(2)\\
\cdots &&\cdots\\
a_{m, 1}x_1+a_{m, 2}x_2+\cdots+a_{m, n}x_n=b_m\pmod{2}&&(m)\\
\end{array}
\right.
$$

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

$$
\left\{
\begin{array}{}
a_{1, 1}x_1\oplus a_{1, 2}x_2\oplus \cdots \oplus a_{1, n}x_n=b_1 &&(1)\\
a_{2, 1}x_1\oplus a_{2, 2}x_2\oplus \cdots \oplus a_{2, n}x_n=b_2 &&(2)\\
\cdots &&\cdots\\
a_{m, 1}x_1\oplus a_{m, 2}x_2\oplus \cdots \oplus a_{m, n}x_n=b_m &&(m)\\
\end{array}
\right.
$$

解异或方程组即可。

其他要求

题目要求:输出一个不超过 $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$ 个目标元素,全部元素都变成当前选取的目标元素的概率。

那么:

$$
p[i]=\frac{i(n-i)}{n(n-1)}p[i-1]+\frac{i(n-i)}{n(n-1)}p[i+1]+(1-2\frac{i(n-i)}{n(n-1)})p[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)}$,那么有:

$$
\begin{aligned}
p[i] &= k\cdot p[i-1]+k\cdot p[i+1]+(1-2k)p[i]\\
2k\cdot p[i] &= k\cdot p[i-1]+k\cdot p[i+1]\\
\end{aligned}
$$

把 $k$ 约掉:

$$
2p[i]=p[i-1]+p[i+1]
$$

也就是:

$$
p[i+1]-p[i]=p[i]-p[i-1]
$$

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

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

$$
p[i]=\frac{i}{n}
$$

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

期望

期望的分析要简单一些,设 $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)}$.

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

$$
p[i]f[i]=p[i]\cdot\frac{n(n-1)}{2i(n – i)} + \frac{1}{2}p[i – 1]f[i – 1]+\frac{1}{2}p[i + 1]f[i + 1]
$$

方程整体的含义是:当前状态下有 $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}$ 代入,整理得到:

$$
\begin{aligned}
f[i] &= \frac{n(n-1)}{2i(n-i)}+\frac{i-1}{2i}f[i-1]+\frac{i+1}{2i}f[i+1]\\
f[i]-\frac{i-1}{2i}f[i-1]-\frac{i+1}{2i}f[i+1]&= \frac{n(n-1)}{2i(n-i)}
\end{aligned}
$$

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

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

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

高斯消元

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

$$
\begin{matrix}
&&\textcolor{gray}{0} &\textcolor{gray}{1} &\textcolor{gray}{2} &\textcolor{gray}{3} &\textcolor{gray}{4}\\
\textcolor{white}{1}\\
\textcolor{gray}{1} &&0 &1 &a &0 &0\\
\textcolor{gray}{2} &&0 &b &1 &c &0\\
\textcolor{gray}{3} &&0 &0 &d &1 &f\\
\textcolor{gray}{4} &&0 &0 &0 &g &1
\end{matrix}
$$

可以发现,对第 $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$,

$$
E_{(i,j)}=[i\neq n]\frac{f_i}{\operatorname{deg_i}} + [j\neq n]\frac{f_j}{\operatorname{deg}_j}
$$

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

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

下面计算 $f_i$,和上面类似地,有:

$$
f_i=
\left\{
\begin{array}{lr}
\sum_{(i, j)\in E,j\neq n}\frac{f_j}{\operatorname{deg}_j}+1, &i = 1\\
\sum_{(i, j)\in E,j\neq n}\frac{f_j}{\operatorname{deg}_j}, &i\neq1\\
\end{array}
\right.
$$

相当于对于每个 $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$ 的期望步数,方程形如:

$$
E_i=
\left\{
\begin{array}{lr}
\sum_{j=1}^n E_jP_{i, j} + 1, &i\neq T\\
0, &i=T
\end{array}
\right.
$$

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

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

参考资料

治疗之雨题解 – 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$。

不在最后一行时:

$$
f_{i, j}=
\left\{
\begin{array}{lc}
\frac{1}{3}(f_{i,j}+f_{i,j+1}+f_{i+1,j})+1, &j=1\\
\frac{1}{4}(f_{i,j}+f_{i,j-1}+f_{i,j+1}+f_{i+1,j})+1, &1 < j < m\\
\frac{1}{3}(f_{i,j}+f_{i,j-1}+f_{i+1,j})+1, &j=m\\
\end{array}
\right.
$$

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

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

消元

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

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

$$
\left\{\begin{array}{cc}
-\frac{2}{3}f_{i,j} + \frac{1}{3}f_{i,j+1} = -\frac{1}{3}f_{i+1,j}-1, &j=1\\
-\frac{3}{4}f_{i,j} + \frac{1}{4}f_{i,j-1} + \frac{1}{4}f_{i,j+1} = -\frac{1}{4}f_{i+1,j} – 1, &1<j<m\\
-\frac{2}{3}f_{i,j} + \frac{1}{3}f_{i,j-1} = -\frac{1}{3}f_{i+1,j}-1, &j=m\\
\end{array}\right.
$$

这样的复杂度变为 $\mathcal{O}(n^4)$。

再观察,其系数矩阵只有主对角线附近有数,其余部分均为 $0$,比如 $m=5$ 时:

$$
\begin{bmatrix}
-\frac{2}{3} & \frac{1}{3} & 0 & 0 & 0\\
\frac{1}{4} & -\frac{3}{4} & \frac{1}{4} & 0 & 0\\
0 & \frac{1}{4} & -\frac{3}{4} & \frac{1}{4} & 0\\
0 & 0 & \frac{1}{4} & -\frac{3}{4} & \frac{1}{4}\\
0 & 0 & 0 & \frac{1}{3} & -\frac{2}{3}\\
\end{bmatrix}=\begin{bmatrix}
-\frac{1}{3}f_{i+1,j}-1\\
-\frac{1}{4}f_{i+1,j}-1\\
-\frac{1}{4}f_{i+1,j}-1\\
-\frac{1}{4}f_{i+1,j}-1\\
-\frac{1}{3}f_{i+1,j}-1\\
\end{bmatrix}
$$

可以用 $\rm{Band-Matrix}$ 继续优化。

这道题中,带的宽度可以看成常数。时间复杂度为 $\mathcal{O}(nm)$,空间复杂度为 $\mathcal{O}(m^2)$ 或 $\mathcal{O}(m)$.

代码

我的代码只保留了每行有用的三列:Ubuntu Pastebin,下面参考资料中的代码保留了整个矩阵。

参考资料

CF24D Broken robot – maoyiting’s blog – 洛谷博客

CF963E – Circles of Waiting

题意

在平面直角坐标系上,有一个神奇的点,一开始在 $(0, 0)$ 。

每秒钟这个点都会随机移动,如果它目前在 $(x, y)$,那么下一秒它:

  • 在 $(x – 1, y)$ 的概率是 $p_1$,
  • 在 $(x, y – 1)$ 的概率是 $p_2$,
  • 在 $(x + 1, y)$ 的概率是 $p_3$,
  • 在 $(x, y + 1)$ 的概率是 $p_4$.

保证 $p_1 + p_2 + p_3 + p_4 = 1$,各次移动互不关联。

求出这个点移动到距离原点距离大于 $R$ 的点的期望步数,对 $10^9+7$ 取模。

欧几里得距离,$0\leq R \leq 50$。

分析

先理解一下题意,下面是 CF官方题解 里的图。

只能在整点上移动,移出半径为 $R$ 的圆为止。

期望DP,设 $f_{x, y}$ 为:从 $(x,y)$ 走出圆所需要的期望步数,方程显然:

$$
f_{x, y}=
\left\{
\begin{array}{lc}
f_{x-1, y}p_1+f_{x, y-1}p_2+f_{x+1, y}p_3+f_{x, y+1}p_4+1, &\sqrt{x^2+y^2}\leq R\\
0, &\sqrt{x^2+y^2}> R
\end{array}
\right.
$$

高斯消元直接解的话,点数是略小于 $4R^2$,时间复杂度是 $\mathcal{O}(R^6)$.

考虑利用 $\rm{Band-Matrix}$ 优化。

如果我们对圆内的点,从左到右,从上到下进行编号。若 $\operatorname{id}(x, y)=x$,则其四周点的 $\operatorname{id}\in[x-2R, x+2R]$.

因此,第 $x$ 列,非零的范围是 $[x-2R, x+2R]$,矩阵是宽度为 $4R$ 的带状矩阵,

消元时只需要考虑向下的 $2R$ 列和向右的 $2R$ 列,消成倒三角矩阵,再回代即可。

这样的时间复杂度是 $\mathcal{O}(R^4)$ 的。未知数个数是 $R^2$ 级别的,消元是 $R\times R$ 级别的。

代码

代码实现上,注意坐标可能为负,细节比较多。

Ubuntu Pastebin

参考资料

这篇比洛谷题解详细:UnnamedOrange – CSDN博客

线性代数入门

这部分差的有点多,赛后再补。

线性变换与矩阵

线性代数的本质 – 03 – 矩阵与线性变换

线性代数的本质 – 04 – 矩阵乘法与线性变换复合

矩阵求逆

求一个 $N\times N$ 的矩阵的逆矩阵。答案对 ${10}^9+7$ 取模。

算法思想

从线性变换的角度理解矩阵和逆矩阵。

逆矩阵表示:把原矩阵变到单位矩阵这一线性变换过程。因此,我们通过高斯消元把原矩阵变换为单位矩阵,同时新建一个矩阵记录变换过程。

算法流程

设 $A$ 是原矩阵,$A^{-1}$ 为 $A$ 的逆矩阵,则 $A\cdot A^{-1}=E_n$,$E_n$ 代表 $n$ 阶单位矩阵。

$$
E=\begin{bmatrix}
1 &0 &\cdots &0 &0 \\
0 &1 &\cdots &0 &0 \\
\cdots &\cdots &1 &\cdots &\cdots \\
0 &0 &\cdots &1 &0 \\
0 &0 &\cdots &0 &1
\end{bmatrix}
$$

若 我们把一个单位矩阵 $E_n$ 并在 $A$ 的右边,之后通过高斯-约旦消元法,把 $A$ 消元成 $E_n$ 的形式,此时 $B$ 就是矩阵 $A$ 的逆。

具体地,以 $n=5$ 为例,把两个矩阵合到一起:

$$
\begin{bmatrix}
A & E_n
\end{bmatrix}=
\left[
\begin{matrix}
a_{1, 1} &a_{1, 2} &a_{1, 3} &a_{1, 4} &a_{1, 5} \\
a_{2, 1} &a_{2, 2} &a_{2, 3} &a_{2, 4} &a_{2, 5} \\
a_{3, 1} &a_{3, 2} &a_{3, 3} &a_{3, 4} &a_{3, 5} \\
a_{4, 1} &a_{4, 2} &a_{4, 3} &a_{4, 4} &a_{4, 5} \\
a_{5, 1} &a_{5, 2} &a_{5, 3} &a_{5, 4} &a_{5, 5}
\end{matrix}
\middle|
\begin{matrix}
1 & & & & \\
&1 & & & \\
& &1 & & \\
& & &1 & \\
& & & &1
\end{matrix}
\right]
$$

通过高斯消元,把左半部分矩阵变成单位矩阵:

$$
\begin{bmatrix}
E_n & A^{-1}
\end{bmatrix}=
\left[
\begin{matrix}
1 & & & & \\
&1 & & & \\
& &1 & & \\
& & &1 & \\
& & & &1
\end{matrix}
\middle|
\begin{matrix}
b_{1, 1} &b_{1, 2} &b_{1, 3} &b_{1, 4} &b_{1, 5} \\
b_{2, 1} &b_{2, 2} &b_{2, 3} &b_{2, 4} &b_{2, 5} \\
b_{3, 1} &b_{3, 2} &b_{3, 3} &b_{3, 4} &b_{3, 5} \\
b_{4, 1} &b_{4, 2} &b_{4, 3} &b_{4, 4} &b_{4, 5} \\
b_{5, 1} &b_{5, 2} &b_{5, 3} &b_{5, 4} &b_{5, 5}
\end{matrix}
\right]
$$

此时矩阵 $B=A^{-1}$.

行列式

给定一个 $n$ 阶行列式 $A$,求 $|A|$。结果对 $p$ 取模。

行列式

对于一个 $n$ 阶矩阵,有:

$\operatorname{det}A=\sum\limits_{p}(-1)^{\tau(p)}\prod\limits_{i=1}^na_{i,p_i} $,其中 $p$ 是任意一个排列,$\tau(p)$ 指的是 $p$ 中的逆序对数。但这个定义暂时没啥用。

矩阵 $A$ 的行列式可以表达为 $|A|$.

性质

建议先看 3b1b 的视频:线性代数的本质 – 05 – 行列式,再看下面的性质。

以下内容参考 MIT公开课 – 行列式笔记线性代数公开课 – MIT 18.06 Linear Algebra – 系列合集 – 哔哩哔哩.

性质 $1$

$|E|=1$,$E$ 为单位矩阵。直接用代数定义就可以证明。

性质 $2$

交换矩阵的两行,行列式的值变为相反数。也直接用代数方法证明。

性质 $3.1$

矩阵中的一行乘系数 $t$,等价于整个行列式乘系数 $t$,即:

$$
t\cdot
\left|\begin{array}{ccc}
a_1 & a_2 & a_3\\
b_1 & b_2 & b_3\\
c_1 & c_2 & c_3\\
\end{array}\right|
=
\left|\begin{array}{ccc}
t\cdot a_1 & t\cdot a_2 & t\cdot a_3\\
b_1 & b_2 & b_3\\
c_1 & c_2 & c_3\\
\end{array}\right|
$$

性质 $3.2$

对于每一行而言,行列式是线性的,即:

$$
\left|\begin{array}{ccc}
a_1 & a_2 & a_3\\
b_1 & b_2 & b_3\\
c_1 & c_2 & c_3\\
\end{array}\right|
+
\left|\begin{array}{ccc}
d_1 & d_2 & d_3\\
b_1 & b_2 & b_3\\
c_1 & c_2 & c_3\\
\end{array}\right|
=
\left|\begin{array}{ccc}
a_1+d_1 & a_2+d_2 & a_3+d_3\\
b_1 & b_2 & b_3\\
c_1 & c_2 & c_3\\
\end{array}\right|
$$

注意 $|A+B|\neq|A|+|B|$.

性质 $4$

若存在两行相等,则行列式为 $0$;若存在两行成倍数关系,则行列式为 $0$.

证明:交换这两行,行列式值变号,又因为行列式值不变,所以 $\operatorname{det}=0$.

性质 $5$

消元不影响行列式的值。消元:第 $i$ 行减去第 $j$ 行的若干倍。

$$
\begin{array}{cl}
&\left|\begin{array}{ccc}
a_1 & a_2 & a_3\\
b_1 & b_2 & b_3\\
c_1 – k\cdot a_1& c_2 – k\cdot a_2& c_3-k\cdot a_3\\
\end{array}\right|\\
\underset{\text{Theory 3.2}}{\longrightarrow}&
\left|\begin{array}{ccc}
a_1 & a_2 & a_3\\
b_1 & b_2 & b_3\\
c_1\cdot a_1& c_2& c_3\\
\end{array}\right|
+
\left|\begin{array}{ccc}
a_1 & a_2 & a_3\\
b_1 & b_2 & b_3\\
-k\cdot a_1& – k\cdot a_2 &-k\cdot a_3\\
\end{array}\right|\\
\underset{\text{Theory 4}}{\longrightarrow}&
\left|\begin{array}{ccc}
a_1 & a_2 & a_3\\
b_1 & b_2 & b_3\\
c_1\cdot a_1& c_2& c_3\\
\end{array}\right|
+
0
\end{array}
$$

性质 $6$

若行列式有一整行为 $0$,则行列式为 $0$。

是性质 $3$ 中的 $t=0$ 的特殊情况。

性质 $7$

倒三角矩阵行列式的值,等于对角线元素的乘积,所以只与对角线上的数有关。

$$
\left|\begin{array}{ccc}
x & x & x\\
& x & x\\
& & x\\
\end{array}\right|
\underset{\text{Eliminate}}{\longrightarrow}
\left|\begin{array}{ccc}
x & & \\
& x & \\
& & x\\
\end{array}\right|
$$

形如上面的矩阵,通过消元转化为更简形式即可。

求解

根据性质 $5$ 和性质 $7$,直接高斯消元即可。注意每次交换行时,需要$\operatorname{Ans}\leftarrow -\operatorname{Ans}$.

int Gauss() {
	int det = 1;
	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;
                //  a[col][i] = (a[col][i] - a[row][i] * t      ) % p;
				}
				for(int i = 1; i <= n; i++) swap(a[col][i], a[row][i]);
				det *= -1;
			}
		}
	}
	for(int i = 1; i <= n; i++) det = det * a[i][i] % p;
    return (det + p) % p;
}

LGV引理

LGV引理

参考 OI Wiki,OIer 不需要证明,能完全理解定理内容就不错了。

定义如下

  • $G$,一张带有边权的有向无环图
  • $v_e$, 边 $e$ 的边权
  • $\omega(P)$,对于一个依次经过 $u_1,u_2\cdots, u_k$ 的有向路径 $P(u_1\rightsquigarrow u_k)$,$\omega(P)$ 表示其所有边权之积
  • $e(u, v)=\sum\limits_{P: u\rightsquigarrow v}\omega(P)$,表示 $u$ 到 $v$ 的每一条路径 $P$ 的 $\omega(P)$ 之和
  • $A=\{a_1, a_2,\cdots a_n\}$,起点集合;$B=\{b_1, b_2,\cdots b_n\}$,终点集合。
  • $S=\{S_1,S_2,\cdots,S_n\}$,是路径的集合,代表 $n$ 条 $A\rightarrow B$ 的不相交路径。形式化地,可以用一个排列 $\sigma(S)$ 来表示,使得 $S_i$ 代表路径 $A_i\rightsquigarrow B_{\sigma(S)_i}$,这组路径满足:$\forall i\neq j$,$S_i$ 和 $S_j$ 无公共点。
  • $N(\sigma(S))$,表示排列 $\sigma(S)$ 的逆序对个数。

引理

对于矩阵:

$$
M =
\begin{bmatrix}e(A_1,B_1)&e(A_1,B_2)&\cdots&e(A_1,B_n)\\ e(A_2,B_1)&e(A_2,B_2)&\cdots&e(A_2,B_n)\\
\vdots&\vdots&\ddots&\vdots\\
e(A_n,B_1)&e(A_n,B_2)&\cdots&e(A_n,B_n)
\end{bmatrix}
$$

其行列式满足:

$$
\det(M)=\sum\limits_{S:A\rightarrow B}(-1)^{N(\sigma(S))}\prod\limits_{i=1}^n \omega(S_i)
$$

其中 $S:A\rightarrow B$ 代表:枚举每一组路径(满足上文要求的)。

证明略,下面两道题会说到 LGV 引理的应用方法,

模板题

题意

有一个 $n\times n$ 的棋盘,左下角为 $(1,1)$,右上角为 $(n,n)$,若一个棋子在点 $(x,y)$,那么走一步只能走到 $(x+1,y)$ 或 $(x,y+1)$。

现在有 $m$ 个棋子,第 $i$ 个棋子一开始放在 $(a_i,1)$,最终要走到 $(b_i,n)$。问有多少种方案,使得每个棋子都能从起点走到终点,且对于所有棋子,走过路径上的点互不相交。输出方案数 $\bmod\ 998244353$ 的值。

两种方案不同当且仅当存在至少一个棋子所经过的点不同。

分析

方格图,每次只能向下或向右,不妨设 $a_i$ 和 $b_i$ 均为单调上升的。

因为引理要求路径不相交,所以唯一的 $\sigma(S)=(1, 2,\cdots, n)$,$N(\sigma(S))=0$,也就是 $a_i$ 和 $b_i$ 配对。

设每条边的边权均为 $1$,则 $\forall \omega(e)=1$,所以:

$$
\det(M)=\sum\limits_{S:A\rightarrow B}(-1)^{N(\sigma(S))}\prod\limits_{i=1}^n \omega(S_i)=\sum\limits_{S:A\rightarrow B}(-1)^0=\sum\limits_{S:A\rightarrow B}1
$$

右式即为题目所求。

构造矩阵,$e(a_i,b_j)=\binom{b_j-a_i+n-1}{n-1}$,高斯消元求其行列式即可。

[NOI2021] 路径交点

题面 太长就不放了。

同样地,设每条边的边权均为 $1$,则 $\forall \omega(e)=1$,所以:

$$
\det(M)=\sum\limits_{S:A\rightarrow B}(-1)^{N(\sigma(S))}\prod\limits_{i=1}^n \omega(S_i)=\sum\limits_{S:A\rightarrow B}(-1)^{N(\sigma(S))}
$$

引理:两条路径交点个数的奇偶性,与将其起点和终点直接相连的交点个数的奇偶性相同。

因此,若我们用 LGV 引理的 $\sigma(S)$ 表示一组路径,若 $N(\sigma(S))\bmod 2=0$,则有路径偶数个交点,反之亦然。

本题求:偶数个交点的方案数量 $-$ 奇数个交点的方案数量,这恰好对应式子中的 $(-1)^{N(\sigma(S))}$.

因此,直接构造矩阵 $M$ 并求行列式,$e(i, j)$ 表示从第一层 $i$ 点到最后一层 $j$ 点的路径数量。

求路径数量可以DP,或者记忆化搜索,不是这道题的难点。

参考资料:NOI 2021 D1T2 题解 – ix35_ 的博客 – 洛谷博客

Matrix-Tree 定理

基尔霍夫矩阵

基尔霍夫矩阵,又称拉普拉斯矩阵,用于描述一张图的某些属性。

无向图

给定一张简单无向图 $G$,其包含 $n$ 个顶点 $v_1, v_2\cdots, v_n$,其拉普拉斯矩阵 $L$ 为:

$$
L_{i,j}=
{\begin{cases}\deg(v_{i})&{\mbox{if}}\ i=j\\-1&{\mbox{if}}\ i\neq j\ {\mbox{and}}\ v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}}\end{cases}}
$$

也就是说,若设 $D$ 为图的度数矩阵,$A$ 为图的邻接矩阵,则等价地有:

$$
L=D-A
$$

下面是一个对于无向图的例子:

度数矩阵邻接矩阵基尔霍夫矩阵
${\textstyle \left({\begin{array}{rrrrrr}2&0&0&0&0&0\\0&3&0&0&0&0\\0&0&2&0&0&0\\0&0&0&3&0&0\\0&0&0&0&3&0\\0&0&0&0&0&1\\\end{array}}\right)}$${\textstyle \left({\begin{array}{rrrrrr}0&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{array}}\right)}$${\textstyle \left({\begin{array}{rrrrrr}2&-1&0&0&-1&0\\-1&3&-1&0&-1&0\\0&-1&2&-1&0&0\\0&0&-1&3&-1&-1\\-1&-1&0&-1&3&0\\0&0&0&-1&0&1\\\end{array}}\right)}$

有向图

有向图存在两个基尔霍夫矩阵,分别为出度基尔霍夫矩阵 $L^\text{out}$ 和入度基尔霍夫矩阵 $L^\text{in}$.

其含义与无向图类似,设图 $G$ 的出度矩阵为 $D^\text{out}$,入度矩阵为 $D^\text{in}$,则有:

$$
L^\text{out}=D^\text{out}-A\\
L^\text{in}=D^\text{in}-A
$$

定理内容

规定:两个生成树不同,当且仅当存在一条边的被包含情况不同。

定理仅适用于无重边、无自环的情况。

无向图

设 $t(G)$ 为无向连通图 $G$ 的生成树个数。

设 $L$ 为无向连通图 $G$ 的基尔霍夫矩阵,任选 $i$,从 $L$ 中删去第 $i$ 行和第 $i$ 列,构造出矩阵 $L^{\prime}$,则:

$$
t(G)=\det L^{\prime}
$$

如图 $G$ 的基尔霍夫矩阵为 $L=\left[{\begin{array}{rrrr}2&-1&-1&0\\-1&3&-1&-1\\-1&-1&3&-1\\0&-1&-1&2\end{array}}\right]$,则 $L^{\prime}$ 可以为 $L^{\prime}=\left[{\begin{array}{rrrr}2&-1&-1&0\\-1&3&-1&-1\\-1&-1&3&-1\\0&-1&-1&2\end{array}}\right]$.

 

有向图

当根固定时,有向图的生成树分为根向生成树叶向生成树,顾名思义,根向生成树的每条边都指向根叶向生成树的每条边都指向根

设 $t^\text{root}(G,s)$ 为以 $s$ 为根节点的根向生成树个数, $t^\text{leaf}(G,s)$ 为以 $s$ 为根节点的叶向生成树个数。

设 $L^\text{out}$ 和 $L^\text{in}$ 为有向连通图 $G$ 的基尔霍夫矩阵,从中删去第 $k$ 行第 $k$ 列后的矩阵为 ${L^\text{out}}^{\prime}(k)$ 和 ${L^\text{in}}^{\prime}(k)$.

钦定 $k$ 为所统计生成树的根节点,则有:

$$
t^\text{root}(G,s)=\det{L^\text{out}}^{\prime}(s)\\
$$
$$
t^\text{leaf}(G,s)=\det{L^\text{in}}^{\prime}(s)\\
$$

所以,有向图的根向树形图个数为 $\sum_{u} t^\text{root}(G,u)$,叶向同理

简要证明

参见 Kirchhoff’s theorem – Proof outline – Wikipedia.

参考资料

Laplacian matrix – WikipediaKirchhoff’s theorem – Wikipedia.

还有例题:[HEOI2015] 小Z的房间.

一些资料

评论

  1. Ranger_CW
    Macintosh
    已编辑
    9月前
    2022-3-05 16:43:31

    ZYCTC AK IOI

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇