题解 P2222 【[HNOI2001]矩阵乘积】

想到了这道题的两个解法，来发一下题解 我们假设所有矩阵都是 $n \times n$ 的，因为就算不是我们也可以通过补 $0$ 变为 $n \times n$ - **稀疏矩阵快速乘法** 稀疏矩阵的定义题目中已经给出了，也就是只有 $m$ 个点有值，剩余点都是 $0$ 的矩阵（$m$ 与 $n$ 同阶） 那么考虑计算 $A \times B = C$，$C_{i,j} = \sum\limits_{k = 1}^n A_{i,k} \times B_{k,j} $ 显然只有 $A_{i,k},B_{k,j}$ 都有值的时候，计算它才是有必要的，否则贡献为 $0$ 所以现在就是要想办法去除无用计算 考虑对第 $i$ 行开一个 `vector`，记录这一行那些位置有值，值都是多少 对第 $j$ 行也是类似操作，记录这一列那些位置有值，值都是多少 然后我们用类似归并的顺序来计算 $C_{i,j}$ 分析一下复杂度，$A$ 的第 $i$ 行在乘法过程中会被用 $n$ 次，$B$ 的第 $j$ 列在乘法过程中也会被用 $n$ 次 所以复杂度就是：$\sum\limits_{i = 1} ^ n cA_i \times n + \sum\limits_{j = 1} ^ n cB_j \times n$ $cA_i$ 表示 $A$ 矩阵第 $i$ 行有值的数量，$cB_j$ 表示 $B$ 矩阵第 $j$ 列有值的数量 显然 $\sum\limits_{i = 1} ^ n cA_i = m$，$\sum\limits_{j = 1} ^ n cB_j = m$，所以在 $n,m$ 同阶的情况下，我们得到了一个 $n ^ 2$ 矩阵乘法 但缺陷在于，两个稀疏矩阵相乘后，结果很可能不是稀疏矩阵了 - **单点求矩阵乘法结果** 当我们在两个矩阵相乘的结果上，只求一个点的点值的话，那么显然不需要求出所有点值 实际上，如果我们要求 $(x,y)$ 的值的话，只需要将 $A$ 矩阵的第 $x$ 行与 $B$ 矩阵的第 $y$ 列相乘就可以了 进一步得，我们实际上只需要知道 $A$ 矩阵的第 $x$ 行和 $B$ 矩阵的第 $y$ 列就可以了 上面这句话是什么意思呢？看下一段你就知道了~ - **本题的加强版** 就是在本题的题意下，把 $3$ 个矩阵相乘，改为 $8$ 个矩阵相乘，数据范围不变（当然时限、空限可能得略微开大） 显然这样你直接套上面两个做法都不行了，需要结合起来 设 $8$ 个矩阵分别为 $A_0,A_1,A_2,A_3,A_4,A_5,A_6,A_7$，结果为 $D$ 那么 $D = A_0 \times A_1 \times A_2 \times A_3 \times A_4 \times A_5 \times A_6 \times A_7$ 根据矩阵结合律，得到 $$D = ((A_0 \times A_1) \times (A_2 \times A_3)) \times ((A_4 \times A_5) \times (A_6 \times A_7))$$ $A_0 \times A_1$，$A_2 \times A_3$，$A_4 \times A_5$，$A_6 \times A_7$，都是两个稀疏矩阵相乘，可以直接 $n ^ 2$ 得出答案，我们设结果为 $B_0,B_1,B_2,B_3$ $D = (B_0 \times B_1) \times (B_2 \times B_3)$ 再次设 $B_0 \times B_1 = C_0,B_2 \times B_3 = C_1$ 因为我们要求 $D_{x,y}$，所以我们只需要知道 $C_0$ 的第 $x$ 行和 $C_1$ 的第 $y$ 列就可以了 而 $C_0$ 的第 $x$ 行，$C_1$ 的第 $y$ 列，朴素计算就是 $n ^ 2$ 的 最后把它们 $O(n)$ 地乘起来，就得到答案了 总复杂度还是 $O(n ^ 2)$ 的，非常的优秀 再多我就不会了，但是感觉这个 $8$ 矩阵相乘也挺好了 - **本题题解** 蛤？$8$ 矩阵相乘你会了，$3$ 矩阵相乘你不会？ ~~但是因为这题读入太迷惑了，所以我没有去写过~~ 读入的话可以去看隔壁的题解，这里就不讲啦