关于 OI 中的一些线性代数知识

1. 矩阵与向量

1.1 定义

• 矩阵：$n$ 行 $m$ 列的方阵就是一个 $n\times m$ 的矩阵，通常用大写字母表示。特别的，当 $n=m$ 时，称这个矩阵为 $n$ 阶方阵。
• 向量：$1$ 行 $m$ 列的矩阵称为行向量，$m$ 行 $1$ 列的矩阵称为列向量。下文若无特殊说明，均为列向量，用 $\vec a$ 表示。

$$\begin{bmatrix}2&3&4 \\ 1&2&3\end{bmatrix}$$

$$\begin{bmatrix}2&3&4\end{bmatrix}$$

• （主）对角线：在 $n$ 阶方阵中，$a_{1,1},a_{2,2},\cdots,a_{n,n}$ 这些左上角到右下角的元素。
• 反对角线：右上角到左下角。
• 单位矩阵：主对角线均为 $1$ 的方阵。有性质：$AI=A$。
• 行阶梯形：(1) 每一非零行中首个非零元为 $1$。(2) 第 $k$ 行元不全 $0$ 时，第 $k+1$ 行首变量之前零的个数多于第 $k$ 行首变量之前 $0$ 的个数。(3) 所有元素为 $0$ 的行在不为零行之后。

1.2 运算

• 加法：适用于两个大小相同的矩阵。$A+B=C \iff A_{i,j}+B_{i,j}=C_{i,j}$
• 数乘：$B=cA\iff B_{i,j}=cA_{i,j}$
• 转置：将矩阵进行反转。$(A^T){j,i}=A{i,j}$。

$$A=\begin{bmatrix}&a_{11}&a_{12}&\cdots&a_{1m}\\&a_{21}&a_{22}&\cdots &a_{2m}\\ &\vdots&\vdots&\vdots&\vdots&\\&a_{n1}&a_{n2}&\cdots&a_{nm}\end{bmatrix}$$

$$A^T=\begin{bmatrix}&a_{11}&a_{21}&\cdots&a_{n1}\\&a_{12}&a_{22}&\cdots &a_{n2}\\&\vdots&\vdots&\vdots&\vdots&\\&a_{1m}&a_{2m}&\cdots&a_{nm}\end{bmatrix}$$

• 矩阵乘法：对于大小为 $nm$ 与 $mp$ 的矩阵 $A$、$B$，定义 $C=A\times B\iff C_{i,j}=\sum\limits_{k=1}^mA_{i,k}\times B_{k,p}$，即乘法结果是一个 $n\times p$ 的矩阵 $C$。
• 逆矩阵：对于方阵 $A$，定义 $A^{-1}$ 为其逆矩阵当 $AA^{-1}=A^{-1}A=I$ 时。并不是所有方阵都有逆。

不懂？

换种方式理解试试。

我们把 $A$ 矩阵看作是 $n$ 个长度为 $m$ 的行向量，$B$ 矩阵看作是 $r$ 个长度为 $m$ 的列向量。而向量的点积形式为：$\vec a\cdot\vec b=\sum\limits_i a_ib_i$。于是 $C_{i,j}$ 的值就是 $A$ 矩阵第 $i$ 个行向量与 $b$ 向量第 $j$ 个向量点积的值。

然后来点运算律？

• $(AB)^T=B^TA^T$ 算一下就好了。
• 交换律：$A+B=B+A$ 乘法是不满足的，为啥就举个例子思考下呗。
• 结合律：$A\oplus(B\oplus C)=(A\oplus B)\oplus C$ 对乘法加法都满足。
• 结合律：$A\times(B+C)=A\times B+A\times C$

1.3 应用

1.3.0 矩阵幂

下文中, 我们默认对 $n$ 阶方阵 $A$ 进行 $k$ 次幂运算, 且代码中出现的 $\text{Matrix}$ 类初始均为单位矩阵。

快速幂

类比实数快速求幂的方法, 在 $\mathcal O(\log k)$ 的复杂度内计算。我们亦可用快速幂在 $\mathcal O(n^3\log k)$ 计算一个 $n$ 阶方阵的 $k$ 次幂。也就是将幂次二进制分组快速计算。

cpp 代码示例如下。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Matrix qpow (Matrix base, int k) {
    Matrix ret; ret.init (base.n, base.n); 
    // ret is a n * n identity matrix
    while (k) {
        if (k & 1) ret = ret * base;
        base = base * base;
        k >>= 1;
    }
    return ret;
}

光速幂

对于固定底数的矩阵运算, 可以采用分块司想。我们按照 $B$ 进制分组, 预处理出 $B^0$, $B^1$, $\cdots$, $B^k$ 的 $k\le B$ 倍幂, 在 $\mathcal O(n^3\log_Bk)$ 的复杂度在线查询。预处理的复杂度为 $\mathcal O(Bn^3\log_B k)$, 这里的 $k$ 为询问中最大幂次。

实际上, 我们经常将光速幂用于优化 $\mathcal{O}(n^3)$ 至 $\mathcal{O}(n^2)$ 的运算中。我们维护一个转移矩阵 $A$, 以及答案向量 $f$。我们设最终答案为 $A^k\cdot f$。我们需要求出 $A^k$, 但实际上, 在求解 $A^k$ 的过程中, 可以维护 $f$, 这样就可以将 $\mathcal O(n^3\log_B k)$ 的复杂度降为 $\mathcal O(n^2\log_B k)$。

cpp 代码示例如下。

1
2
3

for (int i = 2; i <= B; i ++) f[0][i] = f[0][i - 1] * f[0][1];
for (int i = 1; i <= B; i ++) f[1][i] = f[1][i - 1] * f[0][B];
for (int i = 1; i <= B; i ++) f[2][i] = f[2][i - 1] * f[1][B];

值得注意的是, 选择不同的块长, 以获得更优复杂度, 在 $n$ 较大的题目中, 我们一般采用 $B=2$ 作为块长。

1.3.1 矩阵加速递推

Fibonacci 数列

设 $f_0=0,f_1=1$, $f_n=f_{n-1}+f_{n-2}$, 求 $f_k$ 对 $10^9+7$ 取模的结果。其中$k\le 10^{18}$。

这是矩阵加速的最为经典的应用, 注意到递推过程可以写作矩阵形式:

​ $$\begin{bmatrix}f_{i+1} \\ f_{i}\end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0\end{bmatrix}\begin{bmatrix}f_i \\f_{i - 1}\end{bmatrix}$$

因此, 我们只需设转移矩阵 $A= \begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}$, 初始向量 $f_0=\begin{bmatrix}1\\0\end{bmatrix}$, 那么答案即为 $(A^k\cdot f_0)_{1,1}$, 矩阵快速幂即可。

OI-Wiki 例

$f_1=f_2=0$, $f_n=7f_{n-1}+6f_{n-2}+5n+4\times 3^n$。求 $f_k$。

同样的, 我们只需找到转移矩阵 $A$ 以及答案向量 $f$ 即可。

$$A=\begin{bmatrix}7&1&0&0&0\\6&0&0&0&0\\5&0&1&0&0\\12&0&0&3&0\\5&0&1&0&1\end{bmatrix}\ f=\begin{bmatrix}f_{n}\\f_{n-1}\\n\\3^n\\1\end{bmatrix}$$

1.3.2 矩阵表达修改

P4314 CPU 监控 pushup 部分

共有 $n$ 个数, $q$ 次操作。每次操作可以进行区间加, 区间修改操作。也可以查询区间查询历史以及当前最值。$n,q\le 10^5$。

直接做需要进行大量的分类讨论, 但借助矩阵转移可以大大降低思维难度。我们定义类矩阵乘法:

$$A\oplus B=\max\limits_{k=1}^m a_{i,k}+b_{k,j}$$

对于序列中每一个数, 维护 $a,b$ 表示当前值以及历史最值。那么区间加 $k$ 相当于: $\begin{bmatrix}a’ \\b’\end{bmatrix}=\begin{bmatrix}a+k\\\max(b,a+k)\end{bmatrix}=\begin{bmatrix}k & -\infty\\k & 0\end{bmatrix}\begin{bmatrix}a\\b\end{bmatrix}$。但是这题有修改操作, 我们只需再加一维:

$$\begin{bmatrix}a’\\b’\\0\end{bmatrix}=\begin{bmatrix}k\\\max(b,k)\\0\end{bmatrix}=\begin{bmatrix}-\infty & -\infty & k \\-\infty & 0 & k \\-\infty & -\infty & 0\end{bmatrix}\begin{bmatrix}a\\b\\0\end{bmatrix}$$

最后在线段树上维护矩阵即可。

P4719 动态DP

动态查询给定树修改某个点的权值后的最大权独立集的权值大小, $Q\le10^5$ 次。

这道题就是 P1352 一题的带修版。我们考虑这道题的转移式。设 $f_{i,1/0}$ 表示以 $i$ 为根, 选/不选点 $i$ 的答案, $a_i$ 为 $i$ 的权值。显然有 $f_{i,1}=a_i+\sum\limits_{u\in son_i}f_{u,0}$, $f_{i,0}=\sum\limits_{u\in}\max{f_{u,0},f_{u,1}}$。

对于这道带修版, 我们仍然设 $f_{i,1/0}$ 表示以 $i$ 为根, 选/不选点 $i$ 的答案。再设 $g_{i,1/0}$ 表示以 $i$ 为根, 选/不选点 $i$ 的答案(且不选重儿子)。设 $v$ 是节点 $i$ 的重儿子, 我们有：

$$g_{i,0}=\sum\limits_{u\in son_i\land u\not=v}\max{f_{u,0},f_{i,1}}$$

$$g_{i,1}=a_i+\sum\limits_{u\in son_i\land u\not=v}\max{f_{u,0},f_{i,1}}$$

$$f_{i,0}=g_{i,0}+\max{f_{v,0},f_{v,1}}$$

$$f_{i,1}=g_{i,1}+f_{v,0}=\max{g_{i,1}+f_{v,0},-\infty}$$

如法炮制地定义类矩阵乘法:

​ $$A\oplus B=\max\limits_{k=1}^m a_{i,k}+b_{k,j}$$

于是我们将转移写成矩阵的形式。那么便有：

$$\begin{bmatrix}f_{i,0}\\f_{i,1}\end{bmatrix}=\begin{bmatrix}g_{i,0} & g_{i,0} \\ g_{i,1} & -\infty\end{bmatrix}\begin{bmatrix}f_{v,0} \\ f_{v,1} \end{bmatrix}$$

在第二个 dfs 中, 我们可以直接计算出 $f$ 和 $g$ 的结果, 照着上面来一遍即可。

代码中的 $g$ 即为转移矩阵。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

void dfs2 (int x, int top) {
    tp[x] = top;
    id[x] = ++ tim; dfn[tim] = x; ed[top] = max (ed[top], tim);

    f[x][0] = 0, f[x][1] = a[x];
    g[x].M[0][0] = g[x].M[0][1] = 0; g[x].M[1][0] = a[x];
    if (son[x]) {
        dfs (son[x], top);
        f[x][0] += max (f[ son[x] ][0], f[ son[x] ][1]);
        f[x][1] += f[ son[x] ][0];
    }
    for (auto v : G[x]) {
        if (id[v]) continue;
        dfs (v, v);
        f[x][0] += max (f[v][0], f[v][1]);
        f[x][1] += f[v][0];
        g[x].M[0][0] += max (f[v][0], f[v][1]);
        g[x].M[0][1] = g[x].M[0][0];
        g[x].M[1][0] += f[v][0];
    }
}

接下来考虑带修。

不妨设修改的点为 $u$, 修改成的权值为 $w$, 那么 $g_{u,1}$ 应该加上 $w-a_u$, 并 $a_u\gets w$。

和正常树剖一样, 从 $u$ 点往上跳, 这里我们存了两个临时矩阵 $former$ 与 $latter$ 分别表示修改前的 $u$ 至其链顶 的 $f$ 矩阵及修改后的 $f$ 矩阵。

将 $u$ 点跳到其所在链的链顶的父亲 $fa$, 那么根据重链的定义, 边 $(u,fa)$ 必定是一条轻边, 也就是说 $u$ 及其子树 $S_u$ 会对 $g$ 做出贡献。

对于 $g_{fa,0}$, 其余不变, 仅修改 $S_u$ 这一子树的 $f$。因此我们仅需 加上变化值 即可。而状态转移式决定了我们的方式, 但稍微思考, 便知先取 $\max{g_{u,0},g_{u,1}}$ 再做差。

对于 $g_{fa,1}$, 由于不取 $u$, 故直接用 $latter$ 与 $former$ 做差即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

void path_upd (int u, int w) {
    g[u].M[1][0] += w - a[u];
    a[u] = w;
    Matrix former, latter;
    while (u) {
        former = T.query (1, id[ tp[u] ], ed[ tp[u] ]);
        T.upd (1, id[u]);
        latter = T.query (1, id[ tp[u] ], ed[ tp[u] ]);
        int fa = fa[ tp[u] ];
        g[fa].M[0][0] += max (latter.M[0][0], latter.M[1][0]) - 
        max (former.M[0][0], former.M[1][0]);
        g[fa].M[0][1] = g[fa].M[0][0];
        g[fa].M[1][0] += latter.M[0][0] - former.M[0][0];
    }
}

答案即为根节点最值。

NOI2020 美食家

给出有向图, 每个边 $u\to v$ 有长度 $w$, 表示 $u$ 到 $v$ 需要 $w$ 天的时间。每去一个点都会获得愉悦值 $a_i$, 多次经过可以多次获得。特别的, 有 $k$ 个活动, 即第 $i$ 天中到达 $u$ 可以额外获得 $j$ 的愉悦值。从 $1$ 出发, 求恰旅游 $T$ 天, 回到 $1$ 的最大愉悦值。$n\le 50,T\le10^9,w\le 5,k\le200$。

设 $t$ 时刻在点 $u$ 的最大愉悦值为 $f_{t,u}$, 那么有 $f_{t,u}=\max\limits_{(v,u,w)\in G} f_{t-w,v}+c_u$, 若 $t$ 时刻 $u$ 有美食节, 加上额外贡献即可。考虑拆点, 将路径长为 $w$ 的边拆为多个点, 那么上式即为 $f_{t,u}=\max\limits_{(v,u)\in G} f_{t-1,v}+c_u$。由此, 下文所写的边, 都视作 $w=1$。

考虑广义的矩阵乘法, 我们定义对于 $n\times m$、$m\times r$ 的矩阵 $C=A\oplus B$ 为 $C_{ij}=\max\limits_{1\le k\le m}(A_{ik}+B_{kj})$, 这样, 我们即可用矩阵乘法的形式表示状态转移。

具体来说, 对于我们所设 $f_t=\begin{bmatrix}f_{t1}\\f_{t2}\\\vdots\\f_{tn}\end{bmatrix}$, 根据我们定义的矩阵乘法, 考虑如何构造转移矩阵 $G$。当 $u$ 可以转移到 $v$ 时, 当且仅当存在边 $(u,v)$。我们设 $u\to v$ 的边权为 $c_v$, 即 $G_{uv}=c_v$。若直接使 $f_{t+1}=G\oplus f_t$, 我们发现乘积的结果意义不明, 因为 $G_{uv}$ 的意义是 $u$ 向 $v$ 的结果。我们建反图即可。也就是对于所有边 $(u,v)$, 令 $G_{vu}=c_v$, 也就是相当于将这个矩阵转置了。这样, $G$ 的每一行也就代表着到达某一点的权了。对于 $k=0$, 答案即为 $(G^T\oplus f_0)_{1,1}$。

实际上, 我们令 $G_{vu}=c_u$ 亦可。这是因为我们最后的答案形成的路径必然是一个环, 具有一定的对称性。

接下来考虑 $k\not=0$ 的情况。其实和 $k=0$ 异曲同工。我们只需按照时间排序, 对于每个间隔 $delta=T-t$, 令 $now\gets G^{delta}\oplus now$ 即可。复杂度为 $\mathcal O((nw)^3\sum\log delta)$, 无法接受。

预处理出 $G^1,G^2,G^4,\cdots,G^{2^{29}}$ 的结果, 最后在计算时便可实现 $\mathcal O((nw)^2\log T)$ 的复杂度。

1.3.3 定长路径计数

AtCoder Edu.DP R

给出邻接矩阵, $G_{ij}=1/0$ 表示存在/不存在边 $i\to j$, 求长度为 $K$ 的路径数。$n\le 50,K\le 10^{18}$。

考虑 DP。令 $f(i,j)$ 表示长度为 $i$ 终点为 $j$ 的路径总数。那么有 $f(i,j)=\sum\limits_{u=1}^n G(u,j)\times f(i-1,u)$。

考虑降维, 即 $f(j)=\sum\limits_{u=1}^n G(u,j)\times f_{last}(u)$, 这和矩阵乘法的形式不谋而合。那么 $f_{ans}=G^K f_0$, $f_0$ 初始为长度为 $n$ 的列向量, 初值均为 $1$。答案即为 $f_{ans}$ 各数之和。

[SCOI2009] 迷路

给出邻接矩阵, 边有边权 $w$, 求 $1\to n$ 有多少长度为 $t$ 的路径。$n,w\le 10,t\le 10^9$。

我们只需拆点, 这样就会形成 $wn$ 个点的边权为 $1$ 的新图。这样转化为了上一题。

[SDOI2009] HH 去散步

给出 $m\le60$ 条无向边, 不能连续经过一条边。求 $s\to e$ 的路径数。

前两道例题我们都采用点矩阵的方式维护, 这道题我们考虑\textbf{边矩阵}。

我们只需将原图关系映射到一个由边组成的矩阵上即可实现。下面用链式前向星说明构造方法。

设 $cnt=0$, 我们先加入 $0\to s$ 这条边, 这是这是题设的一部分。后每次加入一条无向边 $u\to v$, 编号相邻, 且互为与 $1$ 异或值。我们在构造矩阵时, 只需使 $i\not=j\operatorname{XOR} 1$ 就令 $G_{ij}=1$。接下来操作同上。答案为 $\sum\limits_{to_j=e}G_{1j} $。

2. 高斯消元

2.0 矩阵的初等变换

初等行变换：

• 交换两行
• 一行乘上非零标量
• 一行若干倍加到另一行

初等列变换也同理。

2.1 求解线性方程组

解方程： $$\begin{cases}a_{1,1}x_1+a_{1,2}x_2+\cdots+a_{1,n}x_n=b_1\\a_{2,1}x_1+a_{2,2}x_2+\cdots+a_{2,n}x_n=b_2\\\cdots\\a_{m,1}x_1+a_{m,2}x_2+\cdots+a_{m,n}x_n=b_m\end{cases}$$

显然，可以化作矩阵形式：$A\vec x=\vec b$。$A$ 是系数矩阵。

其中 $[A|\vec b]$ 是增广矩阵。

对于增广矩阵做初等行变换，方程组解不变。

所谓高斯消元法 (Gauss Elimination) 就是通过初等行变换使矩阵化为行阶梯形。

而高斯-约旦消元法 (Gauss-Jordan Elimination) 就是在高斯消元后，反向消元，使矩阵化为行最简形。

2.1.1 解的判断

当消元出现行如：$\begin{bmatrix}0&0&\cdots&|&1\end{bmatrix}$ 时，方程组无解。

除此以外，方程组必有解。

特别的，当消元后非零行构成严格三角形方程组，方程组必然有唯一解。

2.1.2 矩阵求逆

判断是否存在逆使 $AA^{-1}=A^{-1}A=I$。

类似的，不妨使增广增广矩阵为 $[A|I]$。

我们通过高斯消元，使 $A$ 变为行阶梯形，当其可逆时，当且仅当 $A$ 有唯一解。因此此时 $A$ 必然是严格的上三角矩阵。

接下来将 $A$ 通过初等行变化为 $I$，那么这个增广矩阵就变成了 $[I|A^{-1}]$。

这是因为我们对 $A$ 进行的变换相当于多个线性变换，根据 $AI=A$，对于 $A$ 变换的同时，$I$ 同时变换成了 $A^{-1}$。

从这里我们可以得到一个充要结论：方阵可逆，解唯一。

2.1.3 随机游走

给定 $n$ 点有向图，从 $1$ 出发，每次等概率选一条出边。期望到 $n$ 点的步数。

设 $f_i$ 为从 $i$ 出发期望多少步走到 $n$ 点，有 $f_i=\dfrac{\sum\limits_{i\to v\in E}f(v)}{deg_i}+1$。

用高斯消元解这个方程组就好了。

3. 线性空间 & 线性组合 & 线性基

3.0 …空间？

• 一维：数轴。向量表示：$\vec a=\begin{bmatrix}a_1\end{bmatrix}$
• 二维：平面直角坐标系。向量表示：$\vec a=\begin{bmatrix}a_1\\a_2\end{bmatrix}$
• 三维：空间直角坐标系。向量表示：$\vec a=\begin{bmatrix}a_1\\a_2\\a_3\end{bmatrix}$

呃呃，四维是啥？

可惜我们局限于三维世界，无法直观体验四维空间。但可以预见地发现，四维下的向量表示为 $\vec a=\begin{bmatrix}a_1\\a_2\\a_3\\a_4\end{bmatrix}$。

那么 $n$ 维空间，也就对应着一个 $n$ 维向量。容易发现空间内的点与向量是一一对应的，因此我们不妨暂时地把这俩东西当作相同。

3.1 线性空间（向量空间）

数学化的定义：一个向量集合 $V$ 若 $\forall \vec a,\vec b\in V$ 满足： $$\vec a+\vec b\in V$$ $$\lambda\vec a\in V$$ 那么 $V$ 就是一个线性空间。

3.2 线性组合

对于 $n$ 个向量 $\vec v_1,\vec v_2,\cdots,\vec v_n$，设 $c_i$ 为常数，那么 $\sum\limits_{i=1}^n c_i\vec v_i$ 就是它们的一个线性组合。

线性相关与线性无关

对于 $n$ 个向量 $\vec v_1,\vec v_2,\cdots,\vec v_n$，若存在一种系数不全为 $0$ 的线性组合，使得 $\sum\limits_{i=1}^n c_i\vec v_i=0$，那么称这些向量是线性相关的。 更容易理解的，如若通过数乘与相加运算可以将不包含第 $i$ 个的向量通过另 $n-1$ 个向量表示出来，那么这组向量就是线性相关的。

线性无关的定义类似，也就是不存在上述的线性组合。

3.3 张成空间（span）

$n$ 个向量 $\vec v_1,\vec v_2,\cdots,\vec v_n\in S$ 所构成的全体线性空间 $V$ 即为这 $n$ 个向量张成出的空间。 $$V=\operatorname{span}(\vec v_1,\vec v_2,\cdots,\vec v_n)$$

反之，任何一个线性空间都可以表示为 $n$ 个向量的全体线性组合。

这 $n$ 个向量称为线性空间的 生成元。 一组线性无关的生成元，称为一组 基。基的大小称作维数 $\dim V$。 显然易见，线性基是 线性无关 的。

3.4 基坐标

事实上，我们平常使用的平面直角坐标系是以两个垂直的单位向量作为基底，这两个向量张成出的空间便是这个平面，平面上点的坐标也便是我们所说的 基坐标。

下面给个定义。

对于一个线性空间 $V$，若 $\vec v_1,\vec v_2,\cdots,\vec v_n$ 是其一组基底，那么对于 $V$ 中任意向量： $$\vec x=c_1\vec v_1+c_2\vec v_2+\cdots+c_n\vec v_n$$ $(c_1,c_2,\cdots,c_n)$ 就是 $\vec x$ 在 $\vec v_1,\vec v_2,\cdots,\vec v_n$ 这组基下的坐标。

3.5 线性基

下面是 OI 中的线性基，通常解决异或类问题。

如果有 $n$ 个向量 $n$，不存在不全 $0$ 的序列 $a$ 满足：

$$\sum\limits_{i=1}^n a_iv_i=0$$

那么称这 $n$ 个向量「线性无关」。否则为「线性相关」。 对于异或线性基，即不存在异或和为 $0$ 的非空子集。

3.5.1 构造线性基

从大到小枚举每一个二进制位，设第 $a_v$ 为第 $v$ 位的线性基。假设当前插入的值为 $val$，$a_v>0$ 时，$val\gets a_v\operatorname{XOR}val$，继续枚举；反之，令 $a_v\gets val$，退出。

3.5.2 例题

P4151 [WC2011] 最大XOR和路径

• Trick：异或两次相当于没有操作。

于是我们先对原图跑一次生成树，对于所有环，插入线性基。最后我们以 $xorsum_{1\to n}$ 为 $base$ 跑线性基 $\max$ 即可。

code

P3292 [SCOI2016] 幸运数字

• 线性基类似 $\max/\min$，可以合并。

Algorithm 1：考虑树剖，维护每一条重链的线性基，可以做到 4log。 Algorithm 2：考虑倍增，类似 LCA 的方式维护 $u$ 第 $1,2,4,8,\cdots$ 级祖先的线性基。可以做到 $\mathcal O(n\log n\log^2 V+q\log^2 n\log V)$。 Algorithm 3：考虑淀粉质，但我不会写。

code

前缀/后缀线性基

CF1100F Ivan and Burgers

3.6 秩

向量组的秩： $\operatorname{rank}(S)=\dim\operatorname{span}(S)$

矩阵的秩：$\operatorname{rank}(A)$ 为矩阵列向量张成空间的维数，显然行秩与列秩相同。

对于 $n$ 阶方阵 $A$，当 $\operatorname{rank}(A)=n$ 时，称其满秩，此时矩阵可逆。

*4. 线性变换

呃呃，什么是线性变换？

• 变换后原点位置不变
• 只会进行拉伸或者反转，不会使直线变成曲线。

这的确是一种极其简单的理解。

实际上，每一个线性变换都可以用 矩阵乘法 表示，如：$f(\vec x)=A\times\vec x$，这就是一种线性变换。 而前面已经说过，矩阵乘法具有结合律，于是复合的线性变换即可如下计算：

$$f(g(\vec x))=A\times(B\times\vec x)=AB\times\vec x$$

线性变换与坐标系

实际上，线性变换还有更强的作用。

在空间中，我们实际上可以把线性变换矩阵 $A$ 所有列向量认为是原来空间中的基经过线性变换后的新坐标。而将向量 $\vec x$ 进行变换，也就是在新的基坐标下进行再次的对应。

$$\begin{bmatrix}a&b\\c&d\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}=x\begin{bmatrix}a\\c\end{bmatrix}+y\begin{bmatrix}b\\d\end{bmatrix}$$

这段几何意义上的变换，可以看看 3b1b 的视频，可以增进对线性组合这一行为的理解。

通过这个变换法则，我们还可以做出如下酷炫的行为！

• 逆时针旋转 $\theta$：$\begin{bmatrix}\cos\theta&-\sin\theta\\\sin\theta&\cos\theta\end{bmatrix}$

希望大家能够从两种视角来深入理解线性代数中的这一部分，而不是简单了解它对于计算便利的作用。

5. 行列式

用于衡量高维空间的“有向体积”。

学习相关的一些定理后，其实会发现行列式是一种「广义容斥」。

5.1 定义

对于 $n$ 阶方阵 $A$，定义其行列式：

$$\det(A)=\sum\limits_{\sigma\in S_n}\operatorname{sgn}(\sigma)\prod\limits_{i=1}^na_{i,\sigma(i)}$$

其中 $S_n$ 为长度为 $n$ 的全排列集合，$\sigma$ 是其中一个排列。当排列的逆序对数为奇时，$\operatorname{sgn(\sigma)}=-1$。反之， $\operatorname{sgn(\sigma)}=1$。

类似的，积和式的定义为：

$\operatorname{perm}(A)=\sum\limits_{\sigma\in S_n}\prod\limits_{i=1}^na_{i,\sigma(i)}$

在 $\bmod 2$ 意义下，$\operatorname{perm}(A)=\det(A)$，这是由于 $-1\equiv1\pmod 2$。

5.2 性质

5.2.1 初等代数变换对 $\det$ 的影响

• 矩阵转置，行列式不变。
• 行 (列) 交换，行列式取反。
• 行 (列) 的 $k$ 倍加到另一行 (列) 上，行列式不变。
• 行 (列) 数乘 $k$，行列式等比例变大。

5.2.2 简单性质

• 单位化：$\lvert I\rvert=1$。

• 线性性：$\begin{vmatrix}a_{11} & \cdots & pa_{1i}+qb_{1i}&\cdots&a_{1n}\\\vdots&\vdots&\vdots&\vdots&\vdots\\a_{n1} & \cdots & pa_{ni}+qb_{ni}&\cdots&a_{nn}\end{vmatrix}=p\begin{vmatrix}a_{11} & \cdots & a_{1i}&\cdots&a_{1n}\\\vdots&\vdots&\vdots&\vdots&\vdots\\a_{n1} & \cdots & a_{ni}&\cdots&a_{nn}\end{vmatrix}+q\begin{vmatrix}a_{11} & \cdots & b_{1i}&\cdots&a_{1n}\\\vdots&\vdots&\vdots&\vdots&\vdots\\a_{n1} & \cdots & b_{ni}&\cdots&a_{nn}\end{vmatrix}$

  对于行也适用。

• $\det (AB)=\det(A)\det(B)$

• 满秩时行列式不为 $0$。

• 对于上三角矩阵的行列式，其值等于主对角线乘积。

5.2.3 求法

通过初等代数边换，得到上三角矩阵。

最后 $\prod a_{ii}$ 即为行列式值。

取模时，若模数非质数不存在逆元，需要对两行 (列) 辗转相减消元。

模板题 。

5.3 Matrix-Tree 定理

Matrix-Tree 通常用于解决生成树计数问题。

5.3.1 无向图的矩阵树定理

设 $D$ 为无向图的度数矩阵（即 $D_{ii}=deg_i$，其余情况为 $0$），$E$ 为无向图的邻接矩阵。记 $L=D-E$，$L$ 就是「Laplace 矩阵 (Laplacian Matrix)」。设 $K’$ 为 $K$ 的 $n-1$ 阶主子式，也就是 $K$ 同时去掉任意第 $i$ 行第 $i$ 列后的矩阵（因为在连通图中，去掉任意一行一列后行列式值不变）。

那么该无向图的生成树个数就是 $\deg K’$。

5.3.2 有向图的矩阵树定理

既然是有向图，那么自然会分成内向树和外向树。设根为 $R$。

设 $D_{in}$ 为有向图入度矩阵，$D_{out}$ 为有向图的出度矩阵。

$L_{in}=D_{in}-G$，$L_{out}=D_{out}-G$。$L’{in},L’{out}$ 为去掉 $R$ 行 $R$ 列后的矩阵，那么外向生成树的个数为 $\det L’{in}$，内向生成树的个数为 $\det L’{out}$。

5.3.3 生成树的边权积之和

一条边 $(u,v,w)$ 可以看作是有 $w$ 条重边 $(u,v)$，因此可转化为普通的生成树计数。

可以拓展到实数，以下是实数边权的 Cpp 代码。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

double det () {
    double sgn = 1;
    for (int i = 1; i < n; i ++) {
        if (!L[i][i]) 
            for (int j = i + 1; j < n; j ++)
                if (L[j][i]) {
                    swap (L[j], L[i]);
                    sgn = -sgn;
                    break ;
                }
        for (int j = i + 1; j < n; j ++) {
            double div = L[j][i] / L[i][i];
            for (int k = i; k < n; k ++)
                L[j][k] = L[j][k] - div * L[i][k];
        }
    }
    double ret = 1;
    for (int i = 1; i < n; i ++)
        ret = ret * L[i][i];
    return ret * sgn;
}

5.3.4 生成树的边权和之和

我们只需使维护的值变为多项式 $1+wx$ 即可。最终答案就是求 $\bmod x^2$ 下的最高次系数。

考虑如何高斯消元。对于两个多项式 $A+Bx$ 与 $C+Dx$，加减乘操作是简单的。

对于除法操作，$\dfrac {A+Bx}{C+Dx}\equiv\dfrac{(A+Bx)(C-Dx)}{C^2-(Dx)^2}\equiv\dfrac AC+\dfrac{BC-AD}{C^2}x$ 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

modll det () {
    int sgn = 1;
    for (int i = 1; i < n; i ++) {
        if (!L[i][i].a.x)
        for (int j = i + 1; j < n; j ++) {
            if (L[j][i].a.x) {
                sgn = -sgn;
                swap  (L[j], L[i]);
                break ;
            }
        }

        for (int j = i + 1; j < n; j ++) {
            poly div = L[j][i] / L[i][i];
            for (int k = i; k < n; k ++)
                L[j][k] = L[j][k] - div * L[i][k];
        }
    }
    poly res = {1, 0};
    for (int i = 1; i < n; i ++) res = res * L[i][i];
    return res.b * sgn;
}

这里的 modll 是一个剩余系类。

5.3.5 例题

P4336 [SHOI2016] 黑暗前的幻想乡

我们先求全集的生成树个数，接下来考虑容斥。

这是一个十分经典的子集反演形式。设 $f_S$ 表示至多选集合 $S$ 内边集的方案数，$g_S$ 为恰选 $S$ 集合内所有边集至少一个的方案数。那么有：

$f_S=\sum\limits_{T\subseteq S}g_T\iff g_S=\sum\limits_{T\subseteq S}(-1)^{\lvert S\rvert+\lvert T\rvert}f_T$

注意到 $f_S$ 是好求的，我们只要在做 Matrix-Tree 时把 $S$ 包含的边放到 Laplace 矩阵里即可。

之后容斥即可。时间复杂度 $\mathcal O(2^nn^3)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

int U = 1 << (n - 1); modll ans = 0; 
for (int i = 0; i < U; i ++) {
    ll pocount = 0;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
            L[i][j] = 0;
    for (int j = 0; j < n - 1; j ++) 
        if (i >> j & 1) {
            ++ pocount;
            for (auto [u, v] : e[j])
                L[u][u] = L[u][u] + 1, L[v][v] = L[v][v] + 1, L[u][v] = L[u][v] - 1, L[v][u] = L[v][u] - 1;
        }
    pocount = n - pocount - 1;
    if (pocount & 1) pocount = p - 1;
    else             pocount = 1;
    ans = ans + det () * pocount;
}

P6624 [省选联考 2020 A 卷] 作业题

枚举 $\gcd$，考虑容斥。由 $\varphi*1=\operatorname {id}$，所求即为 $\sum\limits_{e\in T} w_e\times\sum\limits_{d\mid w_1,d\mid w_2,\cdots}\varphi(d)$。

枚举 $d$，那么即为 $\sum\limits_{d}\varphi(d)\sum\limits_{e\in T’}w_e$，这里的 $T’$ 中树边权均被 $d$ 整除。

考虑 5.3.4 中的计数方法，发现这个复杂度是 $\mathcal O(Vn^3)$ 的，显然过不了。

当 $d$ 的倍数出现了至少 $n-1$ 次才需要求解，且总因子个数为 $\sum\sigma_0(w_i)$，那么至多有 $\dfrac{\sum\sigma_0(w_i)}{n-1}$ 个 $d$ 合法。这是一个很松的上界。我们对这些合法的 $d$ 跑 Matrix-Tree 即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

modll ans = 0ll;
for (int i = 1; i <= mx; i ++) {
    ll phi = getPhi (i);
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)   
            L[i][j] = {0, 0};
    int tmp = 0;
    for (auto [u, v, w] : edge) {
        if (w % i) continue;
        ++ tmp;
        L[u][u] = L[u][u] + (poly){1, w};
        L[v][v] = L[v][v] + (poly){1, w};
        L[v][u] = L[v][u] - (poly){1, w};
        L[u][v] = L[u][v] - (poly){1, w};
    }
    if (tmp < n - 1) continue;
    ans = ans + det () * phi;
}

P3317 [SDOI2014] 重建

就是求 $\sum\limits_{T}\prod\limits_{e\in T}p_e\prod\limits_{e’\not\in T}(1-p_{e’})$。

我们尝试将没有特殊性质的所有边放在外边，有特殊性质的放在里面。

$\begin{aligned}&=\sum\limits_{T}\prod\limits_{e\in T}p_e\dfrac{\prod\limits_{u}(1-p_{u})}{\prod\limits_{e’\in T}(1-p_{e’})}\\&=\prod\limits_{u}(1-p_u)\sum\limits_T\prod_{e\in T}\dfrac{p_e}{1-p_e}\end{aligned}$

前面是个无关系数，后面是 Matrix-Tree 的标准形式。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

scanf ("%d", &n); double ans = 1;
for (int i = 1; i <= n; i ++)
    for (int j = 1; j <= n; j ++) {
        scanf ("%lf", &P[i][j]);
        if (fabs (P[i][j]) < eps) P[i][j] = eps;
        else if (fabs (1 - P[i][j]) < eps) P[i][j] = 1.0 - eps;
        if (j > i) ans *= (1.0 - P[i][j]);
        if (i != j) L[i][j] = P[i][j] / (1 - P[i][j]);
        if (i != j) L[i][i] += L[i][j], L[i][j] = -L[i][j];
    }

printf ("%.6f\n", ans * det ());

5.4 BEST 定理

用于解决欧拉图的欧拉回路计数问题。

5.4.1 定理内容

设 $G$ 为有向欧拉图，那么 $G$ 的不同欧拉回路总数

$$\operatorname{ec}(G)=t^{\operatorname{root}}(G,k)\prod\limits_{v\in V}(\deg (v)-1)!$$

$t^{\operatorname{root}}(G,k)$ 表示 $G$ 中以 $k$ 为根的内向树个数，可以用 Matrix-Tree 定理计算。

由欧拉图的优秀性质，对于任意 $i,j$ 都有 $t^{\operatorname{root}}(G,i)=t^{\operatorname{root}}(G,j)$，且各点度数相同。

5.4.2 例题

还没遇到相关的题目……

5.5 LGV 引理

用于解决 DAG 上不相交路径计数问题。

5.5.1 引理内容

对于一个 DAG，设起点集合 $A={a_1,\cdots,a_n}$，终点集合 $B={b_1,\cdots b_n}$。对于一个有向路径 $P$，定义 $\omega (P)$ 为 $P$ 上边权之积。对于任意顶点 $u,v$，定义 $e(u,v)=\sum\limits_{P:u\to v}\omega(P)$，也就是 $u$ 到 $v$ 的每一条路径的 $\omega (P)$ 之和。

设一组 $A$ 到 $B$ 的路径集合 $S$，且 $\forall i,j$，$S_i$ 与 $S_j$ 无公共点，且每一条路径恰好连接了 $A$ 中的一个数与 $B$ 中一个数，每个顶点恰有一条路径连接。那么 $S$ 的长度必然为 $n$，因此构成一个排列 $\sigma(S)$，$S_i$ 的起点为 $a_i$，终点为 $b_i$。

记 $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\to B}{\operatorname{sgn}(\sigma(S))}\prod\limits_{i=1}^n \omega(S_i)$$

也就是说矩阵行列式的值，等于所有 $\omega(S)$ 的带符号和。

这是因为对于存在逆序对的方案而言，奇逆序对数的方案与另一个偶逆序对数的方案是一一对应的。

对于满足这一性质：

• 当 $\sigma (S)$ 存在逆序对时，路径有交。

那么对于所有的 $i$ 求出 $a_i\to b_i$ 的无交路径计数，就可以使用 LGV 引理。

5.5.2 例题

P6657 【模板】LGV 引理

题设满足了这一性质。

$e(a_i,b_j)$ 直接用组合数，为 $\dbinom{b_j-a_i+n-1}{n-1}$。

答案就是 $\det M$。因为我们所求的是所有 $a_i\to b_i$ 的不交路径计数，显然是没有逆序对的。

P7736 [NOI2021] 路径交点

设第 $i$ 层到第 $i+1$ 层的奇数交点方案为 $f_i$，偶数交点方案为 $g_i$。那么 $(f_if_{i+1}+g_ig_{i+1})-(f_ig_{i+1}+g_if_{i+1})=(f_i-g_i)(f_{i+1}-g_{i+1})$ 为第 $i$ 层到第 $i+2$ 层的答案。

以此类推，第 $1$ 层到第 $k$ 层的答案就是 $\prod\limits_{i=1}^{k-1}(f_i-g_i)$。

因此，我们只需求出每一层的 $f_i-g_i$ 即可。由于交点奇偶性等价于逆序对数奇偶性，因此这实际上就是其邻接矩阵行列式之值，根据 $\det(AB)=\det A\det B$，相当于把邻接矩阵乘积后的行列式值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

while (T --) {
    scanf ("%d%d", &k, &n); int t = n; int sb; n <<= 1; 
    rep (i, 2, k) scanf ("%d", nn + i), n = max (n, nn[i]);
    rep (i, 2, k) scanf ("%d", m + i); ans.identify (); n = t;
    rep (i, 2, k) {
        int u, v;
        Matrix tmp; n = max (nn[i], (i > 2 ? nn[i - 1] : n));
        rep (j, 1, m[i]) scanf ("%d%d", &u, &v), tmp[u][v] = 1;
        ans = ans * tmp;
    } n = t;
    printf ("%lld\n", det ());
}

ABC216H Random Robots

把时间轴看成 y 轴，这就化作了一个网格图。那么每一秒相当于选择：$(x,y)\to(x,y+1)$ 或者 $(x,y)\to(x+1,y+1)$。同时发现这个概率是假的，实际上求出方案数后乘上 $\dfrac 1{2^{nk}}$ 即可。

假设我们确定了单调递增的终点集合 $B$，根据 LGV 引理，那么答案就是 $\sum\limits_{P}\operatorname{sgn}(P)\prod{A_{i,P_i}}$。

这里的 $A_{i,j}$ 表示从 $(0,x_i)$ 走到 $(n,b_j)$ 的方案数，显然为 $\dbinom{n}{b_j-x_i}$。

考虑 dp，设 $f(S,i)$ 表示 $S$ 内的机器人终点在不超过横坐标 $i$ 的方案数。根据写出的答案式，有转移：

$f(S,i)=f(S,i-1)+\sum\limits_{j\in S}f(S-{j},i-1)\times\dbinom{n}{i-x_j}\times\tau(S,i)$

这里的 $\tau(S,i)$：当集合内大于 $i$ 的个数为奇数时，$\tau (S,i)=-1$；当集合内大于 $i$ 的个数为偶数时，$\tau (S,i)=1$。

答案即为 $f(U,n+x_k)\times 2^{nk}$。$U$ 是全集。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

scanf ("%d%d", &k, &n);
for (int i = 1; i <= k; i ++) scanf ("%d", x + i), x[i] ++;
f[0][0] = 1; int U = (1 << k) - 1;

for (int i = 1; i <= x[k] + n; i ++) {
    for (int S = 0; S <= U; S ++) {
        f[S][i] = f[S][i - 1]; bool flag = true;
        for (int j = 0; j < k; j ++)
            if (S >> j & 1) {
                if (x[j] > i) { flag = false; break; }
                modll coes = (__builtin_popcount ((S >> j) ^ 1) & 1) ? (p - 1) : 1;
                f[S][i] = f[S][i] + f[S ^ (1 << j)][i - 1] * comb (n, i - x[j + 1]) * coes;
            }
        if (!flag) {
            f[S][i] = 0;
            continue;
        }
    }
}

printf ("%lld\n", f[U][ n + x[k] ] / ((modll)(2) ^ (n * k)));