例题1：P4035[JSOI2008]球形空间产生器

【题意简化】在一个 $n(\le 10)$ 维空间有一个球体 , 给定球面上 $n+1$ 的坐标，请计算球心位置。

【分析】 由题意可以知道， $\sum_{j=1}^{n}(a_{i,j}-x_j)^2 = R^2 ,i \in [1,n+1]$，其中 $R$ 为球的半径。 相邻之间做差，可以去掉常数 $R$ ,得到 $n$ 个方程。

$\sum_{j=1}^{n}2x_j(a_{i,j}-a_{i+1,j})^ =\sum_{j=1}^{n}(a_{i,j}^2-a_{i+1,j}^2) , i \in [1,n]$

$2(a_{i,j}-a_{i+1,j})$ 是未知量 $x_j$ 的系数 , $\sum_{j=1}^{n}(a_{i,j}^2-a_{i+1,j}^2)$ 是常数，建立增广矩阵，高斯消元就可以求解。

参考代码：点击

例题2：CF24D Broken robot

【题意简化】有一个 $n$ 行 $m$ 列的矩阵，现在有一个机器人在 $(x,y)$，它每一步等概率向左，右，下走或原地不动，但不能走出矩阵，问走到最后一行期望的步数。 $1\le n,m \le 1000$

【分析】

设 $dp[i][j]$ 表示从位置 $(i,j)$ 走到最后一行，所期望行动的次数的期望。

当 $j=1$ 时，机器人不能向左走，$dp[i][j]=\frac{1}{3}(dp[i][j]+dp[i][j+1]+dp[i+1][j])+1$

当 $j=m$ 时，机器人不能向右走，$dp[i][j]=\frac{1}{3}(dp[i][j]+dp[i][j-1]+dp[i+1][j])+1$

当 $2\le j \le m-1$ 时，$dp[i][j]=\frac{1}{4}(dp[i][j]+dp[i][j-1]+dp[i][j+1]+dp[i+1][j])+1$

初值：$\forall j \in [1,M],dp[n][j]=0$

目标：$dp[x][y]$

特殊情况 $m=1$,$dp[i][1]=\frac{1}{2}(dp[i+1][1]+dp[i][1])+1,dp[n][1]=0$ , 可以得到 $dp[i][1]=dp[i+1][1]+2$ ,而 $dp[n][1]=0$ ,可得到 $dp[x][1]=2*(n-x)$

观察上面的状态转移方程，第 $i$ 行只能走到 $i+1$, "行"维度上满足无后效性。但在同一行，机器人可以向左、向右、停在原地，各状态之间互相转移，无法确定转移顺序，可以采用 $DP$ 套高斯消元来解决这种情况。

以行为转移阶段，在计算第 $i$ 行状态，因为第 $i+1$ 行状态已经计算完毕，可以把 $dp[i+1][j]$ 看作已知数。

将上面三个状态转移方程化成如下形式：

$j=1,2dp[i][j]-dp[i][j+1]=dp[i+1][j]+3$

$j=m,2dp[i][j]-dp[i][j-1]=dp[i+1][j]+3$

$1<j<m,3dp[i][j]-dp[i][j+1]-dp[i][j+1]=dp[i+1][j]+4$

把 $dp[i+1][j]$ 看作已知数，状态转移方程中就剩下 $dp[i][1],dp[i][2]...dp[i][m]$ 就是未知量。第 $i$ 行的每个位置可以列出一个方程，共 $m$ 个方程,可以使用高斯消元法解除 $dp[i][1],dp[i][2]...dp[i][m]$ 的值。

但是使用一次普通高斯消元复杂度就是 $O(n^3)$ ，计算 $n$ 行复杂度就是 $O(n^4)$，题目中 $n=1000$，显然超时了。

不过把上述方程系数列出来，我们会发现一些规律，以 $n=5$ ：

$\begin{bmatrix} 2& -1& 0&0 &0 &dp[i+1][1]+3 \\ -1& 3& -1 &0 &0 &dp[i+1][2]+4 \\ 0& -1& 3& -1& 0 & dp[i+1][3]+4\\ 0& 0& -1& 3& -1& dp[i+1][4]+4\\ 0& 0& 0& -1& 2&dp[i+1][5]+3 \end{bmatrix}$

可以发现高斯消元的系数矩阵除主对角线和对角线两侧的斜线之外，其余部分为 $0$ 。在执行高斯消元，每一行实际上只有 $2-3$ 个位置相减，只需要 $O(M)$ 的即可求出各个位置量，总复杂度为 $O(NM)$。

参考代码：点击

例题3：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$

【分析】

求给 $m$ 条边进行编号，获得的得分为边的编号，如果知道了每条边走的次数的期望，那么按照期望从大到小排序，编号逐渐增加，那么总得分期望最小。

要计算每一条边走的次数的期望，可以先计算走过点的期望，设 $f[i]$ 表示走过点 $i$ 的期望次数:

$f[i]=\sum_{(i,j)\in E,j\ne n}\frac{f[j]}{du[j]}$

由于起点在 1 号点，期望次数会加 1

$f[1]=\sum_{(1,j)\in E,j\ne n}\frac{f[j]}{du[j]} + 1$

移项后

$f[i]-\sum_{(i,j)\in E,j\ne n}\frac{f[j]}{du[j]} =0$

$f[1]-\sum_{(1,j)\in E,j\ne n}\frac{f[j]}{du[j]} =1$

$n$ 是终点，不需要计算 $f[n]$,$n-1$ 个式子，$n-1$ 个未知数，可以使用高斯消元法求 $f[i]$ .

设 $g[i]$ 表示经过第 $i$ 条边的期望次数

$g[i]=\frac{f[u]}{du[u]}+\frac{f[v]}{du[v]},st[i]=u,ed[i]=v,u\ne n,v \ne n$

对于 $m$ 条边从按照经过期望次数 $g[i]$ 从大到小排序，经过次数高的分给编号小，可以使得总分最低。

参考代码：点击

例题4：P2011计算电压

【题意简化】给定一个 $n(n \le 200)$ 个点 $m(m\le 2 \times 10^5)$ 条的电路图，边权就为电阻，已知 $k(\le n)$ 个点的电位。$q(\le 10^6)$ 组询问，给定两个点，求这两个点之间流过的电流。

从每个节点流出的电流等于流入的电流。

那么电流如何计算，$I=\frac{U}{R}$，点 $x$ 与 $y$ 之间的电压为 $U=f_x-f_y$,$f_x,f_y$ 为点 $x,y$ 的电势, $U$ 为电势差,即电压，有正有负，负代表反方向。

一个点流入和流出电流总和应该相等，如果考虑正负号，总和应该为 0.

$\sum \frac{f_x-f_y}{R_{xy}}=0$

各个点电势 $f_x$ 未知，可以列 $n$ 个等式,可以使用高斯消元法求解。

对于点 $x$,枚举每一个邻居点 $y$,上面式子，可以化为

$f_x\sum \frac{1}{R_{xy}}-\sum \frac{fy}{R_{xy}}$=0

由于 $f[0]=0$，可以不用考虑负极。

$n$ 个方程，$n$ 个未知量(有 $k$ 个是已知量，当做未知的，赋值成已知)，建立好各个系数后，高斯消元法，直接求解。

参考代码：点击

例题5: P10499 开关问题

【题意简化】有 $n(n \le 29)$ 个相同的开关，每个开关与某些开关存在关联，当打开或关闭某个开关的时候，与之关联的开关状态取反，所有开关之间的关联状态已知。 初始状态已知，经过若干次操作后，使得最后 $n$ 个开关打到特定状态，任意一个开关最多只能进行一次开关操作。请计算存在多少种方法可以达到指定状态。

【分析】

设 $x_i$ 表示第 $i$ 个开关的操作情况， $x_i=1$ 表示按了这个开关，$x_i=0$ 表示没有按。再统计 $a_{i,j}$ 表示 $i$ 个开关和第 $j$ 个开关的关联情况，$a_{i,j}=1$ 表示按下 $j$ 会影响 $i$ 的状态，$a_{i,j}=0$ 表示不会影响，特别地，令 $a_{i,i}=1$ .

开关的初始状态为 $s_i$ , 最终状态为 $d_i$ , 所有与它关联的开关的操作情况执行异或运算得到结果。可以列出异或方程组：

$$\left\{\begin{matrix} a_{1,1}x_1\oplus a_{1,2}x_2\oplus \dots a_{1,1}x_1 = s_1 \oplus d_1 \\ a_{2,1}x_1\oplus a_{2,2}x_2\oplus \dots a_{2,1}x_1 = s_2 \oplus d_2\\ \dots\\ a_{n,1}x_1\oplus a_{n,2}x_2\oplus \dots a_{n,1}x_1 = s_n \oplus d_n \end{matrix}\right.$$

高斯消元法把加减替换成异或，不需要执行乘法。

如果存在 0=1 的方程，无解。否则自由元可以取 0 或 1 ，自由元个数为 $k$ , 答案就是 $2^k$.

为了提高效率，可以将系数矩阵状压。

例题6: [SDOI2010] 外星千足虫

根据题意，可以列出方程：

$\sum f_x\equiv (0/1) \mod 2$

在模2 下加法相当于异或运算,$n$ 个未知数,$m$ 个方程，高斯消元，但高斯消元复杂度就成了 $O(n^2m)$ ,可以使用bitset 压位优化，bitset 异或操作复杂度为 $O(\frac{n}{w})$ ,那么总复杂度就为 $O(\frac{n^2m}{w})$,评测机为32位 $w=32$ ，可以通过。

参考代码：点击

例题7: P4783【模板】矩阵求逆

【分析】每一个初等行变换，都等价于用一个初等矩阵左乘原矩阵。

$A^{-1}\begin{bmatrix} A &I \end{bmatrix}$ ->$\begin{bmatrix} I &A^{-1} \end{bmatrix}$

参考代码：点击

例题8: P7112 【模板】行列式求值

参考：【教程】行列式

---

其他经典题目

学习完毕

{{ select(1) }}

• YES
• NO